day21 最长对称子串
河北大学程序设计训练营[TOC]
day21 最长对称子串对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。
输入格式:输入在一行中给出长度不超过1000的非空字符串。
输出格式:在一行中输出最长对称子串的长度。
输入样例:1Is PAT&TAP symmetric?
输出样例:111
代码:
123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;int main(){ string str; getline(cin,str); int maxLen=0; for(int i=0; i<str.size(); i++)//遍历每一点,以每一点为中心,向左右查看是否相等 { int j=1; while(i-j>=0&&i+j ...
day20 单链表的创建及遍历
单链表的创建及遍历读入n值及n个整数,建立单链表并遍历输出。
输入格式:读入n及n个整数。
输出格式:输出n个整数,以空格分隔(最后一个数的后面没有空格)。
输入样例:在这里给出一组输入。例如:
210 5
输出样例:在这里给出相应的输出。例如:
10 5
注意:
整个题没难度,最基本的单链表建立。注意申请内存空间的malloc函数的使用struct NList* newNode = (struct NList*)malloc(sizeof( struct NList ));
代码123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>#include <malloc.h>using namespace std;struct NList{ int num;//数据域 struct NList* Next;//指针域};int main(){ int n , x; cin >> n; ...
day19 连续因子
题目描述一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。
输入格式:输入在一行中给出一个正整数 N(1<N<2^31)。
输出格式:首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按因子1×因子2×……×因子k的格式输出最小的连续因子序列,其中因子按递增顺序输出,1 不算在内。
输入样例:
630
输出样例:
35*6*7
解题思路:⚠️要注意到连续因子的含义:比如说:630 = 3×5×6×7,连续因子就是5、6、7再看:168的因数有6、7、8,但是6×7×8 = 336发现差别了吧
题解:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <bits/stdc++.h>using namespace std;int main ...
day18 N个数求和
河北大学程序设计训练营[TOC]
2-4 N个数求和 (30分) 本题的要求很简单,就是求N个数字的和。麻烦的是,这些数字是以有理数分子/分母的形式给出的,你输出的和也必须是有理数的形式。
输入格式:
输入第一行给出一个正整数N(≤100)。随后一行按格式a1/b1 a2/b2 …给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外,负数的符号一定出现在分子前面。
输出格式:
输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分,其中分数部分写成分子/分母,要求分子小于分母,且它们没有公因子。如果结果的整数部分为0,则只输出分数部分。
输入样例1:
52/5 4/15 1/30 -2/60 8/3
输出样例1:
3 1/3
输入样例2:
24/3 2/3
输出样例2:
2
输入样例3:
31/3 -1/6 1/8
输出样例3:
7/24
思路:利用结构体 ,分子分母分别相加,进行约分化简,最后根据题目格式输出。
注意点
相加过程中可能使分子或分母超过int型表示范围,因此保险起见,直接用long long来存储好喽。这种情况尤其体现在分数的 ...
day17 求n以内最大的k个素数以及它们的和
河北大学程序设计训练营[TOC]
day17 求n以内最大的k个素数以及它们的和本题要求计算并输出不超过n的最大的k个素数以及它们的和。
输入格式:输入在一行中给出n(10≤n≤10000)和k(1≤k≤10)的值。
输出格式:在一行中按下列格式输出:
1素数1+素数2+…+素数k=总和值
其中素数按递减顺序输出。若n以内不够k个素数,则按实际个数输出。
列举两种方法:
1.适用于判断某个数n是否是素数
把[2,sqrt(n)]中的正数依次作为n的除数,如果存在能整除的,则n不为素数,否则就是素数
1234flag=1;for(i=2;i<=sqrt(n);i++)if(n%i==0)flag=0,break;return flag;
返回值flag判断是否为素数。
2.适用于寻找较大区间内的所有素数
我们知道,素数就是除了1和本身没有因数的数,即素数不存在除了1和本身的因数。则任何一个数都是某个素数倍数(分解质因数)
则从2开始,把2作为第一个素数,将2的所有倍数都标记为非素数(合数),标记完后往上找没有被标记的数,是3,再把3的倍数标记,往上找,4=2*2,找到 ...
day16进制转换(Q进制转换成T进制)
河北大学程序设计训练营[TOC]
day16每日一题讲解题目:
2-2 进制转换(Q进制转换成T进制) (25分)
给定一个整数Q(2<=Q<=10),一个非空字符串,以及另一个整数T(2<=T<=10), 编程要求过滤掉字符串中所有非Q进制数对应的字符组成一个新的字符串,该字符串无正负号,将该字符串表示的Q进制数转换为T进制数的字符串输出。
输入格式:第一行输入一个整数Q, 代表Q进制(2<=Q<=10)
第二行输入以回车结束的一行非空字符串。
第三行输入一个整数T, 代表要转换成T进制
输出格式:输出转换后的T进制数字符串。
输入样例:12310152
输出样例:11111
做题思路:这题属于比较简单的一类题,进制转换可能是每一个学程序的人都会接触到的内容,所以这里就不再赘述了。唯一需要值得注意的一点是,题目中要求 编程要求过滤掉字符串中所有非Q进制数对应的字符组成一个新的字符串,需要过滤的字符可能不止是字符,也有可能是其他符号(包括空格等),所以读入时需要一行getline,去除字符的时候也应该判断这个字符是否在字符的ASCII码内,不然最 ...
day15 最大公约数和最小公倍数
河北大学程序设计训练营[TOC]
day15 最大公约数和最小公倍数本题要求两个给定正整数的最大公约数和最小公倍数。
输入格式:输入在一行中给出两个正整数M和N(≤1000)。
输出格式:在一行中顺序输出M和N的最大公约数和最小公倍数,两数字间以1空格分隔。
输入样例:1511 292
输出样例:173 2044
最大公约数: 解最大公约数常用的是欧几里得算法(辗转相除法) 欧几里得算法指出:设a,b均为正整数,a,b的最大公约数,就等于b,a%b的最大公约数,即 Gcd(a,b)=Gcd(b,a%b)。(可以通过数学方法证明结论。)
最小公倍数: 在求解最大公约数的基础上(假设g是最大公约数),我们可以得到a,b的最小公倍数是 ab/g 。很容易可以发现,a和b的最大公约数是正整数集合a,b的交集部分,而最小公倍数是为正整数集合a,b的并集。要得到并集,由于 ab 会使公因子的部分多计算一次,所以需要除掉一次公因子,就得到了ab/g 的写法。但由于 ab 在计算时可能会溢出,所以写成 a/gb ,g是a,b的最大公约数,因此 a/g 一定可以整除。
123456789101 ...
day14 字符串循环左移
河北大学程序设计训练营
字符串循环左移和之前讲的数组循环左移一样。
注意
有可能比数组长度大。
接收空格字符使用getline(cin,s) ;函数
12345678910111213141516171819202122#include<iostream>#include<string>using namespace std;int main(){ string s; int n , start; getline(cin,s); cin >> n; start = n % s.length(); for(int i=start; i < s.length() ; ++i){ cout << s[i]; } for(int i=0; i < start ; ++i){ cout << s[i]; } }
day13 装箱问题
河北大学程序设计训练营
AC代码1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h> //c++头文件,用这一个就够了,基本包含所有需要的”插件“,string、vector、queue等等using namespace std;int main(){ vector<int>box; int n,volume,site=0; scanf("%d",&n); for(int j=0; j<n; j++) { scanf("%d",&volume); if(box.size()==0) //第一个箱子没放,特殊处理,现在发现没这步操作也行 box.push_back(volume),site=0;//记录索引 else //有箱子 { int i=0; for ...
day12 汉诺塔非递归实现
河北大学程序设计训练营
题目描述:借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为“a”)通过借助柱(标记为“b”)移动到目标柱(标记为“c”),并保证每个移动符合汉诺塔问题的要求。
输入格式:输入为一个正整数N,即起始柱上的盘数。
输出格式:每个操作(移动)占一行,按柱1 -> 柱2的格式输出。
输入样例:
3
输出样例:
a -> ca -> bc -> ba -> cb -> ab -> ca -> c
解题思路:准备:
首先容易证明,当盘子的个数为n时,移动的次数应等于2^n-1。
一位美国学者发现一种出人意料的方法,只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序:
若n为偶数,按顺时针方向依次摆放ABC;
若n为奇数,按顺时针方向依次摆放ACB。
步骤
按顺时针方向把圆盘1从现在的柱子移动到下一根柱子。
即若n为偶数时:(奇数差不多,懒得写了😁)
若圆盘1在柱子A ...