一个正整数可能是由n个连续的整数相加得来(选做)
比如:
15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
从键盘输入一个数s,求出它的所有可能得排列数
算法一:“穷举法”
也称暴力破解法,从1开始找连续的序列,一直累加,一直到接近我们输入的值。
如果能正好等于输入的值,就说明这些累加的顺序是正确的;
否则,如果加起来小于15,则继续加下一个值;
如果大于15,说明这个顺序已经不是了,没有再加下去的必要,结束本次循环。从下一个轮从2开始查找,依次递推。
以15为例,从1开始加:
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5 == 15 ———停止----------------第一轮结束
第二轮从2开始加:
2
2+3
2+3+4
2+3+4+5
2+3+4+5+6 > 15 ————停止-------------第二轮结束
第三轮从3开始加:
3
3+4------------7
3+4+5-----------12
3+4+5+6-----------24 ————停止-----------------第三轮结束
..........................................以此类推
第七轮从7开始加:
7
7+8 ==15 ————停止-------------第七轮结束
第八轮从8开始加:
8
8+9--------------17>15 ————停止-------------第八轮结束
显而易见,后面的值累加一定会大于15.
所以可以总结出规律:n/2+(n/2+1)==15
往后再移一个数:n/2+1+n/2+1+1=======>n+3 已经超过我们输入的值了
所以我们第一轮只需要加到我们输入的 值的一半就好了(假设我们的值是n,一半就是n/2),再往后面加,一定会大于我们的值。所以对应程序这里需要用到一个for循环,循环范围是输入值的一半。表示循环次数。
而每一轮进入之后要与后面的值累加,所以这里又用到一个for循环;这里for循环要达到的目的是:从第一个数往后面开始累加,第二个数开始往后累加...............要怎样达到这个要求呢?可以将这个循环的初值和循环的次数连接起来。
第一次循环——>从第一个数开始加
第二次循环——>从第二个数开始加
所以将第二个循环的初始值与外面的次数联系起来,设n为我们输入的值,i是循环的次数(也是我们需要累加的数值),j表示从哪个数开始累加(从1开始累加),计算累加之和变量,我们用sum去保存表示;这里具体格式可以显示如下:
for(int i=1;i<=n/2;i++)
{
for(int j=i;sum<=n;j++) //特别注意:第二个循环的条件
{ //一定是累加之和小于等于我们输入的值
}
}
这里怎么去显示输出呢?怎样有15=1+2+3+4+5的显示效果呢?
这里再用到一个循环(条件是:在找到加起来的和是我们输入的值时)初始值必须是我们开始相加的值,依次递增,直到加到我们找到的j的值。显示格式可以参考如下:
//输出: 15 = 1 + 2 + 3 + 4 + 5
printf("%d = %d",n,i);//利用k来进行输出
for(k = i+1;k <= j;k++)
{
printf(" + %d",k);
}
至此,我们的框架已经搭建完成!
整体代码如下:
int main()
{
int n;
printf("本程序实现:从键盘输入一个数s,显示它的所有可能的连续排列数\n");
printf("请输入你要累加和的值:");
scanf("%d",&n);
int sum=0;
int i,j,k;
for(i=1;i<=n/2;i++)
{
sum=0;//特别注意:每一轮累加完成总和都要清零
// for(int j=i;j<=n;j++) //理解错误
for(j=i;sum<=n;j++)
{
sum=sum+j;
if(sum==n)
{
printf("%d=%d",n,i);
//为了帮助输出
for(k=i+1;k<=j;k++)//for的初始值是从i的后面一个值开始加,直到加到上个for循环累加的最后一个值(可以等于)
{
printf(" + %d",k);
}
printf("\n");//保证达到预期效果的每个式子换行
//换行的效果也是在如果加和等于我们输入的值的条件下
}
}
}
return 0;
}
算法二:重复利用加和法
在这个算法中,假设l是开始相加的数,r是我们后面相加的数,我们可以观察:
第一次循环:l=1,r=6:1+2+3+4+5=15(成功显示)
从1开始加的数已经完成,不用再判断加下一个数的和,因为肯定会大于我们输入的值;
第二次我们从2开始加,不用一直从2往后依次递加;把上次加起来的和sum利用起来,但是这个sum要减去我们上一次开始相加的数,也就是1;第二次循环:l=2,r=6,sum=15-1=14;
进入循环,14<15,所以要加下一个要加的数r,这里sum=14+6=20>15;
进入if(sum>n)的条件,这里总和减去这轮开始加的数l=2,sum=20-2=18,l=2+1=3;
进行for循环,继续进入if(sum>n)的条件,减去开始加的数l=3,sum=18-3=15;l=3+1=4;
进入for循环,发现sum=n=15;开始输出:15=4+5+6;
............................
依次类推,直到找到所有的连续相加的和等于我们输入的和的序列。
这个算法的精髓是:完美的利用了变化的值和不变的值,以及这个值该在什么时候变化!没有浪费每次求出的总和这个数值,很好的利用起来各个变量。与上一个算法相比,这个算法显得更灵活,不是一个个去尝试,去加和,去比较,再输出。不过上一个算法的好处是能能首先想到的方法,下面的算法相较更需要尝试和思考。
整体代码显示如下:
int main()
{
int l;//第一个开始相加的数
int r;//下一个要加的数
int n;
printf("本程序实现:从键盘输入一个数s,显示它的所有可能的连续排列数\n");
printf("请输入你要累加和的值:");
scanf("%d",&n);
int sum=1;
for(l=1,r=1;l<=n/2;)//这个算法使用两个变量进行变换,循环次数确定,后面的表达式不确定(根据后面条件决定)
{
//每次进行判断sum的值
if(sum<n)//和小于输入的数时
{
r++;
sum=sum+r;
}
else if(sum==n)
{
printf("%d=%d",n,l);
for(int k=l+1;k<=r;k++)
{
printf("+ %d",k);
}
printf("\n");
//找到了以l开头的相加数,输出完之后,找下一个相加数
sum=sum-l;
l++;
}
else if(sum>n)
{
sum=sum-l;
l++;//
}
}
}
这是我在学C语言中,通过老师讲解和询问同学对自己的学习的一个总结,文中有不对或说法不准确的地方,恳请各位大佬指正!
本人的评论区欢迎大家讨论技术性的问题!