试题2(排序).doc

【 1、Ugly Numbers】丑陋数（Ugly number）是仅有素因子 2, 3 或 5的整数。序列1, 2, 3, 4, 5, 6, 8, 9, 10, 12, .给出了前10个丑陋数。按照惯例， 1被包含在丑陋数中。给出整数n，编写一个程序输出第n个丑陋数。输入:输入的每行给出一个正整数n (n 1500)。输入以n=0的一行结束。输出:对于输入的每一行，输出第n个丑陋数，对n=0的那一行不处理。样例输入样例输出12901210注：试题来源：New Zealand 1990 Division I在线测试地址：POJ 1338, UVA 136【2、 排列】大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。任务描述：给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3n。比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。输入：第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 n 1024 )和k(1k64)，第二行有n个正整数，是1，2 n的一个排列。输出：对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。样例输入样例输出33 12 3 13 13 2 110 21 2 3 4 5 6 7 8 9 103 1 21 2 31 2 3 4 5 6 7 9 8 10注： 试题来源：2004 人民大学ACM选拔赛在线测试地址：POJ 1833【 3、Number Sequence】给出一个正整数i。编写一个程序，在数组序列S1S2.Sk中找到第i个位置的数字。每组Sk由从1到k的正整数序列组成，序列中从1到k一个接一个给出。例如，这个序列的前80个数字如下：11212312341234512345612345671234567812345678912345678910123456789101112345678910输入:输入的第一行给出一个整数t (1t10)，表示测试用例的个数，后面每行给出一个测试用例。 每个测试用例给出一个整数i (1i2147483647)。输出:输出每行处理一个测试用例，给出在第i个位置的数字。样例输入样例输出28322注：试题来源：ACM Tehran 2002, First Iran Nationwide Internet Programming Contest在线测试地址：POJ 1019，ZOJ 1410【4、 Whats Cryptanalysis?】 密码分析是破解其他人的加密文本的过程，这有时可能包含对一个（加密）文本的段落进行某种统计分析。你的任务是编写一个程序，对一个给定的文本进行简单的分析。输入:输入的第一行给出一个正十进制整数n，表示后面要输入的行数。后面的n 行每行包含0个或多个字符（可以有空格）。这是要被分析的文本。输出:每个输出行包含一个大写字母，后跟一个空格，然后是一个正十进制整数。整数表示相应的字母在输入文本中出现的次数。在输入中大写字母和小写字母被认为是相同的。其他字符不必被计算。输出排序必须按计数的递减顺序，即，出现次数最多的字母在输出的第一行，输出的最后一行表示出现次数最少的字母。如果两个字母出现次数相等，然后在字母表中先出现的字母在输出中先出现。如果某个字母没有出现在文本中，则该字母不能出现在输出中。 样例输入样例输出3This is a test.Count me 1 2 3 4 5.Wow! Is this question easy?S 7T 6I 5E 4O 3A 2H 2N 2U 2W 2C 1M 1Q 1Y 1注：试题来源：University of Valladolid September 2000 Contest在线测试：UVA 10008【5、Anagram Groups】世界知名的A. N. Agram教授当前的研究是对大量的变形词组进行处理，他为他的英语文本中字符的分布理论找到了一个新的应用。给出一段文本，请你找到最大的变形词组。一段文本是一个单词的序列。单词w是单词v的一个变形词当且仅当存在某个字符位置交换p将w变成v，则w和v在同一变形词组中。变形词组的大小是在这一词组中单词的数量。请找出5个最大的变形词组。 输入:输入的单词由小写字母字符组成，单词由空格或换行符分开，输入由EOF终止。本题设顶不超过30000个单词。输出:输出5个最大的变形词组。如果小于5个词组，就输出所有的词组。词组按大小的递减排序。相同大小按字典顺序。对每个词组，输出其大小和组内的单词。将组内单词按字典次序排列，相同的单词仅输出一次。样例输入样例输出undisplayedtraceteasingletonetaeatdisplayedcratecatercartecaretbetabeatbateateabetGroup of size 5: caret carte cater crate trace .Group of size 4: abet bate beat beta .Group of size 4