算法基本练习

超、凢脫俗 2021-11-29 08:00 524阅读 0赞

**1、数列排序**

问题描述

> 给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200

输入格式

> 第一行为一个整数n。  
> 第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。

输出格式

> 输出一行，按从小到大的顺序输出排序后的数列。

--------------------

\*\*2、特殊回文数\*\* 问题描述

> 123321是一个非常特殊的数，它从左边读和从右边读是一样的。  
> 输入一个正整数n，编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。

输入格式

> 输入一行，包含一个正整数n。

输出格式

> 按从小到大的顺序输出满足条件的整数，每个整数占一行。

--------------------

**3、回文数**  
问题描述

> 1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。

输出格式

> 按从小到大的顺序输出满足条件的四位十进制数。

--------------------

**4、特殊的数字**  
问题描述

> 153是一个非常特殊的数，它等于它的每位数字的立方和，即153=1*1*1+5*5*5+3*3*3。编程求所有满足这种条件的三位十进制数。

输出格式

> 按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。

--------------------

**5、杨辉三角形**  
问题描述

> 杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。  
> 它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。  
> 下面给出了杨辉三角形的前4行：  
> 1  
> 11  
> 121  
> 1331  
> 给出n，输出它的前n行。

输入格式

> 输入包含一个数n。

输出格式

> 输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。

--------------------

**6、查找整数**  
问题描述

> 给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。

输入格式

> 第一行包含一个整数n。 第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。 第三行包含一个整数a，为待查找的数。

输出格式

> 如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。

--------------------

**7、数列特征**  
问题描述

> 给出n个数，找出这n个数的最大值，最小值，和。

输入格式

> 第一行为整数n，表示数的个数。  
> 第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。

输出格式

> 输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。

--------------------

**8、字母图形**  
问题描述

> 利用字母可以组成一些美丽的图形，下面给出了一个例子：  
> ABCDEFG  
> BABCDEF  
> CBABCDE  
> DCBABCD  
> EDCBABC  
> 这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

输入格式

> 输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。

输出格式

> 输出n行，每个m个字符，为你的图形。

--------------------

**9、01字串**

> 问题描述  
> 对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：  
> 00000  
> 00001  
> 00010  
> 00011  
> 00100  
> 请按从小到大的顺序输出这32种01串。

输入格式

> 本试题没有输入。

输出格式

> 输出32行，按从小到大的顺序每行一个长度为5的01串。

--------------------

**10、闰年判断**  
问题描述

> 给定一个年份，判断这一年是不是闰年。  
> 当以下情况之一满足时，这一年是闰年：
> 
> 1.  年份是4的倍数而不是100的倍数；
> 2.  年份是400的倍数。  
>     其他的年份都不是闰年。

输入格式

> 输入包含一个整数y，表示当前的年份。

输出格式

> 输出一行，如果给定的年份是闰年，则输出yes，否则输出no。  
> 说明：当试题指定你输出一个字符串作为结果（比如本题的yes或者no，你需要严格按照试题中给定的大小写，写错大小写将不得分。

--------------------

**11、阶乘计算**  
问题描述

> 输入一个正整数n，输出n!的值。  
> 　　其中n!=1*2*3\*…\*n。

算法描述

> n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A\[0\]表示a的个位，A\[1\]表示a的十位，依次类推。  
> 　　将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。  
> 　　首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

输入格式

> 输入包含一个正整数n，n<=1000。

输出格式

> 输出n!的准确值。

--------------------

**12、高精度加法**  
问题描述

> 输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

算法描述

> 由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。  
> 定义一个数组A，A\[0\]用于存储a的个位，A\[1\]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。  
> 计算c = a + b的时候，首先将A\[0\]与B\[0\]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入>C\[0\]，即C\[0\]等于(A\[0\]+B\[0\])%10。  
> 然后计算A\[1\]与B\[1\]相加，这时还应将低位进上来的值r也加起来，即C\[1\]应该是A\[1\]、B\[1\]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C\[1\]中。依此类推，即可求出C的所有位。  
> 最后将C输出即可。

输入格式

> 输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。

输出格式

> 输出一行，表示a + b的值。

--------------------

**13、Huffuman树**  
问题描述

> Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。  
> 给出一列数\{pi\}=\{p0, p1, …, pn-1\}，用这列数构造Huffman树的过程如下：
> 
> 1.  找到\{pi\}中最小的两个数，设为pa和pb，将pa和pb从\{pi\}中删除掉，然后将它们的和加入到\{pi\}中。这个过程的费用记为pa +pb。
> 2.  重复步骤1，直到\{pi\}中只剩下一个数。  
>     在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。  
>     本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

> 例如，对于数列\{pi\}=\{5, 3, 8, 2, 9\}，Huffman树的构造过程如下：  
> 　　1. 找到\{5, 3, 8, 2, 9\}中最小的两个数，分别是2和3，从\{pi\}中删除它们并将和5加入，得到\{5, 8, 9, 5\}，费用为5。  
> 　　2. 找到\{5, 8, 9, 5\}中最小的两个数，分别是5和5，从\{pi\}中删除它们并将和10加入，得到\{8, 9, 10\}，费用为10。  
> 　　3. 找到\{8, 9, 10\}中最小的两个数，分别是8和9，从\{pi\}中删除它们并将和17加入，得到\{10, 17\}，费用为17。  
> 　　4. 找到\{10, 17\}中最小的两个数，分别是10和17，从\{pi\}中删除它们并将和27加入，得到\{27\}，费用为27。  
> 　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入格式

> 输入的第一行包含一个正整数n（n<=100）。  
> 接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。

输出格式

> 输出用这些数构造Huffman树的总费用。

--------------------

**14、2n皇后问题**  
问题描述

> 给定一个n\*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式

> 输入的第一行为一个整数n，表示棋盘的大小。  
> 接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出格式

> 输出一个整数，表示总共有多少种放法。

--------------------

**15、报时助手**  
问题描述

> 给定当前的时间，请用英文的读法将它读出来。  
> 时间用时h和分m表示，在英文的读法中，读一个时间的方法是：  
> 如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“three o’clock”。  
> 如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。  
> 时和分的读法使用的是英文数字的读法，其中0~20读作：  
> 0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。  
> 30读作thirty，40读作forty，50读作fifty。  
> 对于大于20小于60的数字，首先读整十的数，然后再加上个位数。如31首先读30再加1的读法，读作“thirty one”。  
> 按上面的规则21:54读作“twenty one fifty four”，9:07读作“nine seven”，0:15读作“zero fifteen”。

输入格式

> 输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。

输出格式

> 输出时间时刻的英文。

--------------------

**16、回形取数**  
问题描述

> 回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。

输入格式

> 输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。

输出格式

> 输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。

--------------------

**17、龟兔赛跑预测**  
问题描述

> 话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。  
> 　　然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找到了你——清华大学计算机系的高才生——请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。

输入格式

> 输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)

输出格式

> 输出包含两行，第一行输出比赛结果——一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。  
> 　　第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。

--------------------

**18、芯片测试**  
问题描述

> 有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。  
> 每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。  
> 给出所有芯片的测试结果，问哪些芯片是好芯片。

输入格式

> 输入数据第一行为一个整数n，表示芯片个数。  
> 第二行到第n+1行为n\*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。

输出格式

> 按从小到大的顺序输出所有好芯片的编号

--------------------

**19、FJ的字符串**  
问题描述

> FJ在沙盘上写了这样一些字符串：  
> 　　A1 = “A”  
> 　　A2 = “ABA”  
> 　　A3 = “ABACABA”  
> 　　A4 = “ABACABADABACABA”  
> 　　… …  
> 　　你能找出其中的规律并写所有的数列AN吗？

输入格式

> 仅有一个数：N ≤ 26。

输出格式

> 请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

--------------------

**20、Sine之舞**  
问题描述

> 最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。  
> 　　不妨设  
> 　　An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)  
> 　　Sn=(…(A1+n)A2+n-1)A3+…+2)An+1  
> 　　FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。

输入格式

> 仅有一个数：N<201。

输出格式

> 请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

--------------------

**21、数的读法**  
问题描述

> Tom教授正在给研究生讲授一门关于基因的课程，有一件事情让他颇为头疼：一条染色体上有成千上万个碱基对，它们从0开始编号，到几百万，几千万，甚至上亿。  
> 　　比如说，在对学生讲解第1234567009号位置上的碱基时，光看着数字是很难准确的念出来的。  
> 　　所以，他迫切地需要一个系统，然后当他输入12 3456 7009时，会给出相应的念法：  
> 　　十二亿三千四百五十六万七千零九  
> 　　用汉语拼音表示为  
> 　　shi er yi san qian si bai wu shi liu wan qi qian ling jiu  
> 　　这样他只需要照着念就可以了。  
> 　　你的任务是帮他设计这样一个系统：给定一个阿拉伯数字串，你帮他按照中文读写的规范转为汉语拼音字串，相邻的两个音节用一个空格符格开。  
> 　　注意必须严格按照规范，比如说“10010”读作“yi wan ling yi shi”而不是“yi wan ling shi”，“100000”读作“shi wan”而不是“yi shi wan”，“2000”读作“er qian”而不是“liang qian”。

输入格式

> 有一个数字串，数值大小不超过2,000,000,000。

输出格式

> 是一个由小写英文字母，逗号和空格组成的字符串，表示该数的英文读法。

--------------------

**22、完美的代价**  
问题描述

> 回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。  
> 　　交换的定义是：交换两个相邻的字符  
> 　　例如mamad  
> 　　第一次交换 ad : mamda  
> 　　第二次交换 md : madma  
> 　　第三次交换 ma : madam (回文！完美！)

输入格式

> 第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)  
> 第二行是一个字符串，长度为N.只包含小写字母

输出格式

> 如果可能，输出最少的交换次数。  
> 否则输出Impossible

--------------------

**23、矩形面积交**  
问题描述

> 平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。

输入格式

> 输入仅包含两行，每行描述一个矩形。  
> 在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。

输出格式

> 输出仅包含一个实数，为交的面积，保留到小数后两位。

--------------------

**24、矩阵乘法**  
问题描述

> 给定一个N阶矩阵A，输出A的M次幂（M是非负整数）  
> 　　例如：  
> 　　A =  
> 　　1 2  
> 　　3 4  
> 　　A的2次幂  
> 　　7 10  
> 　　15 22

输入格式

> 第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数  
> 接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

输出格式

> 输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

--------------------

**25、分解质因数**  
问题描述

> 求出区间\[a,b\]中所有整数的质因数分解。

输入格式

> 输入两个整数a，b。

输出格式

> 每行输出一个数的分解，形如k=a1*a2*a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)

--------------------

**26、字符串对比**  
问题描述

> 给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：  
> 　　1：两个字符串长度不等。比如 Beijing 和 Hebei  
> 　　2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing  
> 　　3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing  
> 　　4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing  
> 　　编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。

输入格式

> 包括两行，每行都是一个字符串

输出格式

> 仅有一个数字，表明这两个字符串的关系编号

--------------------

**27、时间转换**  
问题描述

> 给定一个以秒为单位的时间t，要求用“::”的格式来表示这个时间。表示时间，表示分钟，而表示秒，它们都是整数且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，则输出“1:1:1”。

输入格式

> 输入只有一行，是一个整数t（0<=t<=86399）。

输出格式

> 输出只有一行，是以“::”的格式所表示的时间，不包括引号。