今天在KADA的博客看到一篇C算法题,就分析了一下下!这是我个人理解(白话文),就是为了做一下分析记录,话说从CPP以来,除了后续几章的什么队列呀,链表啊之类的我就没看过算法code,今天看了一下,很有兴趣!
![]()
编写一个程序,读入一个正整数(就是不带负号的整数),把所有的连续的(比如:12345!{上山打老虎}),和与给定的正整数相等的正整数们找出来。例如,如果输入为27,于是发现 2+3+4+5+6+7,8+9+10,13+14为27,那么共有3个组合。如果输入的数字是10000,那么就有18加到142,297加到 1328,388加到412以及1998加到2002这4组。
通常的算法是,将所有小于n/2的连续正整数的和的情况算出来与n比较。(为啥N/2?举例一下,比如21吧要是N不/2的话,那么就会有11+12,12+13但是他们和21不相等,所以超过11以后就没有机会相加得21了。所以能就N/2来减少穷举次数,提升程序运行速度啦)
上面和下面的就不废话了,就说中间的那段核心吧.for循环
#include <stdio.h> #include <stdlib.h> void main() { char line[100];//设定一个数组,三个变量,一个计数器 long sum, i, j, n; int count = 0; printf("请输入整数n:");//等待用户输入数字 gets(line); n = atol(line); for(i=1; i<=n/2+1; i++)//说下n/2+1.因为有些特殊的数字比如27,27/2就是13啦,若不加1那么13<=13,循环从这里就over了,所以就没有13+14的这样组合那么就少计数一个组合 { for(sum=i,j=i+1; j<=n/2+1; j++)//因为是连续正整数和,所以j比i永远多1,这就是有j=i+1的由来 { sum += j;//sum=sum+j,i赋值给sum和j相加,类似2+3+4+5+6+7,然后总值赋值给sum. if(sum == n)//由sum和n比较,如果sum=27,也就是2+3+4+5+6+7=27就执行if里面的语句,计数器并加1,跳出里层的for循环,执行外层for。 { printf("%d -- %d\n", i, j); count++; continue; } } } if(count > 0)//for执行完毕后,计数器大于0输出结果 printf("共有%d种连续整数和等于%ld\n", count, n); else printf("没有解\n"); }
就逻辑到这里..还有一种算法比这更好,不过我还未理解!等我理解了再把那种算法分析写出来.这篇日志作为分析记录,若我分析的不对,请指出哦!
C.. 厉害哇!!!
其实N/2的原因是:加到N/2就够了,如果再往后加,光N/2+N/2+1都已经比N还大了。因为int类型/运算向下是取整的,所以这里是<N/2+1,来保证N的一半在无论N是奇数偶数时,都能被计算到。
还是你牛啊,突然发现那个20的例子就是个错误,改改去!
你的主页有点问题。
博客不错,支持一下!
主题不错,不要博客了两篇就阳痿啊!
@Kada 别激动.晚上写文章
[...] 上篇博文分析C语言名题系列:连续整数和正常人思考的算法…就是1+2+3+4+5…然后和N比较,跟N相等就输出不等就不输出… [...]