geslon 发表于 2009-10-8 23:29:02

puzzleup 10.07

Ascending Letters

26 letters of the alphabet are shuffled and listed to form a 26 lettered string. The longest sequence of alphabetically ascending letters (either from left to right or from right to left) in this string is noted. What is the minimum possible number of letters in this sequence?

Two examples for the first seven (A, B, C, D, E, F, G) letters:
Arrangement: BGEDFCA, Longest sequence: GEDCA (ascending from right to left).
Arrangement: DBCAGEF, Longest sequence: BCEF (ascending from left to right)

求助：哪位帮助翻译一下？（我心里明白，但表达不好，怕误导别人。嘿嘿。）

wool 发表于 2009-10-9 08:23:27

数字1~26， 任意不重复排列， 取出其中最长的升序组合（从左往右或者从右往左读均可）
比如 1 2 3 4 5 6 7
随意的一个： 2 7 5 4 6 3 1 其中最长的升序是 7 5 4 3 1（从右往左）
随意的一个： 4 2 3 1 7 5 6 其中最长的升序是 2 3 5 6 （从左往右）
那么从这26个数字组成的所有排列（26!种，汗。。。）中取出其中最长的升序组合， 最短的一种组合包含多少个数字？


PS：我的答案是7
2 15 3 16 4 17 5 18 6 19 7 20 8 14 1 21 9 22 10 23 11 24 12 25 13 26

〇〇 发表于 2009-10-9 09:00:39

2楼翻译不正确，应该是字母表而不是数字

sjymb 发表于 2009-10-9 11:42:01

可以到5

〇〇 发表于 2009-10-9 14:42:35

是要双向取最小值？

〇〇 发表于 2009-10-9 20:05:16

123(12,13,23)
1234(12,13,14,23,24,34,123,124,134,234,1234)

geslon 发表于 2009-10-10 06:50:01

本帖最后由 geslon 于 2009-10-10 06:52 编辑

是双向最大组合的最小值。说起来真拗口。

比如n=4时，bdac组合=2，是最小值。
比如n=7时，cbeadgf组合=3，是最小值。

4楼说可以到5，我不明白，请教下。我最小算到6.

〇〇 发表于 2009-10-10 08:01:13

newkid猜测一下：

最小长度：6
zuvwxypqrstklmnofghijabcde

〇〇 发表于 2009-10-10 09:32:25

round(sqrt(n))?
貌似正确，但怎么严格证明
uvwxyz opqrst ijklmn cdefgh 6789ab 012345
也是6

〇〇 发表于 2009-10-11 20:40:56

不是round,而是向上取整sqrt(n)
分成x组，每组y个都是顺序排列，组组之间逆序排列
可以做到正序y,逆序x
页: [1]
查看完整版本: puzzleup 10.07