解题思路:
看到这道题,我们很容易想到写一个四重循环再if判断。
#include <stdio.h> int main(){ int i; int x,y,n,m,z=0; for(i=0;i<=1000;i++){ z=0; for(x=1;x<i;x++){ for(y=1;y<i;y++){ for(n=1;n<i;n++){ for(m=1;m<i;m++){ if(x+y+n+m==i){ z++; } } } } } printf("%d,%d\n",z,i); } return 0; }
但是这样时间复杂度太高了,对于输入最大数1000来说甚至达到循环10^12次方,提交后时间会超时。
这里给大家提供三种方法。
方法一:打表。
这也是比赛常用的方法,简单来说就是使用一个代码预先得到每一种测试的答案,然后把答案放到一个数组里面,然后直接调用就可以了。
然而用for循环得到答案显然是不现实的,它在处理一百以上的数值就开始吃力了,等它得到所有答案比赛也快结束了。
这里使用递归的方法进行求解:
#include <stdio.h> long long int ans = 0; int dfs(int n, int m) {//n是需要处理的数,m是需要分解成几位 if (m == 1 && n>0){ ans++; return 0; } for (int i = 1; i <= n - m + 1; i++) dfs(n - i, m - 1); } int main() { int n; for (int i = 0; i <= 1000; i++) { dfs(i, 4); printf("%d,\n",ans);//这里需要加上,放到数组时用于分隔 ans = 0; } return 0; }
这个算法在处理800以上的数值速度才开始出现放慢,不过直接用来提交答案还是会“时间超限”。
最后将得到的数据放到数组里面,这才是我们要提交的最终答案:
#include int main() { int n; scanf("%d",&n); int p[1000]={ctrt+v};//把得到的数值Ctrl+c Ctrl+v过来 while(scanf("%d",&n)!=EOF){ printf("%d\n",p[n]); } return 0; }
当然这种方法比较麻烦,递归函数也比较难理解,我还是推荐大家用数学的角度去做题,这样可以减轻大量的工作。
方法二:观察。
观察数值,当n是2,3,4,5,6,7,8,9时
答案是 0,0,1,4,10,20,35而这些数之间的差,0,1,3,6,10,15,而这些差的差是1,2,3,4,5……
是不是很神奇,这样我们就得出他的规律来了
开两组数组,用来存放他们的差和差的差
具体代码如下:
#include <stdio.h> int main() { int i; int n,z=0; scanf("%d",&n); int p[1001]={0,0,0,1,3,6};//答案的差 int l[1001]={0,0,1,2,3,4}; //答案的差的差 while(scanf("%d",&n)!=EOF){ for(i=0;i<n;i++){ if(i>2){//开始有不符合规律的0,需要排除 p[i]=p[i-1]+l[i-1]; z+=p[i]; l[i]=l[i-1]+1; } } printf("%d\n",z); z=0; } return 0; }
方法三:隔板法。
这里需要用到一点高中学过的排列组合的知识,以输入8为例,我们把8分成8个1,依次排开,会得到七个间隔。
用3个隔板放到间隔中,就把这8个1分成了4份,也就是我们需要的四个数。
在七个间隔中任意取三个空位放上隔板,全部的放法有C(7,3)=(7*6*5)/(3*2*1)。
因为题目要求分成四个数,所以一直是三个隔板,即分母上是6一直不变,分子是(n-1)*(n-2)*(n-3)
代码实现如下:
#include <stdio.h> int main() { int n; scanf("%d",&n); while(scanf("%d",&n)!=EOF){ if(n>3)printf("%d\n",(n-1)*(n-2)*(n-3)/6); else printf("0\n"); } return 0; }
0.0分
164 人评分
A+B for Input-Output Practice (V) (C语言代码)浏览:640 |
简单的a+b (C语言代码)浏览:674 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:487 |
1012题解浏览:938 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1483 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:756 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:748 |
检查金币 (C语言代码)浏览:1504 |
1025题 初学者,求帮忙看下,不知道哪错了浏览:325 |
小九九 (C语言代码)浏览:542 |