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 ...
day11 悄悄关注
河北大学程序设计训练营
Day11 每日一题讲解题目
7-4 悄悄关注 (25分)
新浪微博上有个“悄悄关注”,一个用户悄悄关注的人,不出现在这个用户的关注列表上,但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探,根据某人的关注列表和其对其他用户的点赞情况,扒出有可能被其悄悄关注的人。
输入格式:输入首先在第一行给出某用户的关注列表,格式如下:
1人数N 用户1 用户2 …… 用户N
其中N是不超过5000的正整数,每个用户i(i=1, …, N)是被其关注的用户的ID,是长度为4位的由数字和英文字母组成的字符串,各项间以空格分隔。
之后给出该用户点赞的信息:首先给出一个不超过10000的正整数M,随后M行,每行给出一个被其点赞的用户ID和对该用户的点赞次数(不超过1000),以空格分隔。注意:用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户,在点赞信息中也没有重复用户。
输出格式:我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人,很可能是其悄悄关注的人。根据这个假设,请你按用户ID字母序的升序输出可能是其悄悄关注的人,每行1 ...
day10 Swan学院社团招新
河北大学程序设计训练营[TOC]
day10 Swan学院社团招新Swan学院社团招新,招新宣讲会分散在不同时间段,大一新生小花花想知道自己最多能完整的参加多少个招新宣讲会(参加一个招新宣讲会的时候不能中断或离开)。【问题说明】这个问题是对几个相互竞争的招新宣讲会活动进行调度,它们都要求以独占的方式使用某一公共资源(小花花)。调度的目标是找出一个最大的相互兼容的活动集合。 活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。【温馨提示】应先将所有的活动按照结束时间升序排列,然后再选择可能的时间组合,并求出最大的组合数,使用qsort()排序函数是一个不错的选择。qsort 的函数原型是: void qsort(voidbase,size_t num,size_t width,int(__cdeclcompare)(const void,const void)); 功 能: 使用快速排序例程进行排序;头文件:stdlib.h; 参数: 1 待排序数组首地址;2 数组中待排序元素数量;3 各元素的占用空间大小;4 指向函数的指针,用于确定排序的顺序
输入格式:第一行为n,表示有n ...