递归法全排序问题
比如有(1,2,3,4)这样一组数
1.先分成(1)和(2,3,4),然后对(2,3,4)全排列
2.把(1)分别和(2,3,4)中的数对调
3.比如一次调换(2),(1,3,4),然后对(2,3,4)全排列
4.调换的算完了,恢复,变成(1),(2,3,4),再调换下一个(3),(1,2,4)
练习:
一、将一个字符组全排序
Input
一个长度小于10的字符串,该字符串由数字1~9组成。字符不会重复出现。
Output
按数字在输入串中出现的次序从小到大的顺序输出该字符组的全排序
Sample Input
132
Sample Output
1 3 2
1 2 3
3 1 2
3 2 1
2 1 3
2 3 1
二、一天晚上,一对已婚夫妇,和他们的儿子女儿在家里发生了一起谋杀案,凶手、帮凶、被害人和目击者分别是家里的人。情况如下:
(1)目击者和那个帮凶不是同一性别
(2)年龄最大的和目击者不是同一性别
(3)年龄最轻的和被害人不是同一性别
(4)帮凶比受害者大
(5)父亲是年龄最长者
(6)凶手不是家中最年轻的成员
凶手、帮凶、被害人和目击者分别是谁?
算法的基本思路是:定义两个数组,一个数组表示家庭成员,另一个数组表示他们可能扮演的角色。当找出一种排列方式,然后一个数组对另一个数组赋值,如符合题目条件,则进行输出
三、乔治拿来一组等长的木棒,将它们随机地裁断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。(以后讲剪枝时候重点给大家讲解)
Input
输入包含多组数据,每组数据包括两行。第一行是一个不超过64的整数,表示砍断之后共有多少节木棍。第二行是截断以后,所得到的各节木棍的长度。在最后一组数据之后,是一个零。
Output
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
Sample Output
6
5
四、Problem Description
There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)
For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.
Sample Input
1
2
3
Sample Output
1
2
4
五、Problem Description
In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.
Input
Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤n ≤30.
Output
For each test case, output one integer number giving the number of possible tilings.
Sample Input
2
8
12
-1
Sample Output
3
153
六、大整数乘法
计算m位整数乘以n 位整数。(其中M<10,N<10)
poj1035:拼写检查 时间限制: 2000毫秒内存限制: 65536K 提交总数: 11190 : 4140 说明 作为一个新的拼写检查程序的开发团队成员,你写的模块,将检查使用一切形式的所有已知的正确的话字典的 话的正确性。如果这个词在字典中缺席那么它可以取代正确的话(从字典)可以取得下列操作之一: 从单词的一个字母删去 ;在任意一个字母的单词一个字母 取代,插入一个?任意字母到单词 ,你的任务是编写程序,会发现每一个给定的单词从字典中所有可能的替代。 输入 输入文件的第一部分包含从字典中的所有单词。每个字中占有它自己的行。完成这部分是由一个单独的行上的单字符'#' 。所有的字是不同的。将有10000字的字典。 文件的下一部分,包含了所有的单词进行检查。每个字中占有它自己的行。这部分也完成了由一个单独的行上的单字符'#' 。将有最多50个字进行检查。 输入文件中的所有单词(从字典和被检查的词字)只包括小字母字符,每一个包含15个字符最多。 输出 写入到输出文件中完全检查它们在输入文件的第二部分中出现的顺序每个字一行。如果这个词是正确的(即它在字典中存在)写留言:“是正确的“,如果这个词是不正确的,那么先写这两个字,然后写字符。”:“(冒号),并在一个单独的空间写了所有可能的替代品,用空格隔开这些替代应在书面的顺序。其在字典中(在输入文件的第一部分)。出现,如果有这个字没有替换,然后换行,应立即按照冒号。 样例输入 我是有我更多的比赛,我太iF奖#我知道米的较量HAV OO或我的网络连接MRE#
输出范例 我是正确的认识到:奖米:我的我的比赛是正确的甲肝:已经有OO:太:我是正确的FI:我MRE:更多的我 poj3080:蓝色牛仔裤 时间限制: 1000毫秒内存限制: 65536K 提交总数: 6173 接受日期: 2560 说明 基因地理工程是IBM与国家地理学会,是分析,从成千上万的贡献者地图地球是如何填充DNA的研究伙伴关系,作为IBM的研究人员,你一直负责编写一个程序,会发现共性之间个人调查资料,以确定新的遗传标记,可与相关的DNA 片段。DNA碱基序列是指出在它们在分子中发现的顺序列出的氮基地。有四种碱基:腺嘌呤(A),胸腺嘧啶(T),鸟嘌呤(G),胞嘧啶(C)。一个6碱基的DNA序列可以作为TAGACC代表。鉴于一组DNA碱基序列,确定在所有序列中出现的最长的系列基地。 输入 输入到这个问题,将开始与行包含一个单一的整数n表示数据集的数目。每个数据集由以下几部分组成组成: ?一个正整数m(2 <= M <= 10)的碱基序列,在此数据集。 ?m行每片含60个碱基组成的单一碱基序列。 输出 对于每一个输入数据集,输出基地序列的最长共同所有的碱基序列。如果最长的公共子序列的长度小于3基地,显示字符串“没有显着的共性”。如果存在多个子序列相同的长度最长,只输出序列的按字母顺序排列第一。
ACM contests https://www.doczj.com/doc/4113602779.html,