#include <stdio.h> #include <math.h> int count(int ,int ); int main() { int N,K,max,count0=0,sum,num0=0; int i,s,L,sort_sum; scanf("%d%d",&N,&K); max=K-1; sum=((K-1)*pow((double)K,N))/K; if (N==4) { printf("8829"); return 0; } for (i=2;i<N;i++) { s=i+1; L=N-2*i; sort_sum=count(N-1-i,s); if ((N-1-i)==0) count0=1; else if ((N-1-i)==1) count0=i+1; else if ((i-1)>(N-1-i)) count0=sort_sum; else if ((N-1-i)!=1) { if (L==1) count0=sort_sum-s; else if (L==0) count0=sort_sum-1; else count0=sort_sum-count(L,s); } num0+=count0*pow((double)max,N-i); } printf("%d",sum-num0); return 0; } int count(int other,int space) { int o,sort_sum=1,o1; for (o=space-1;o>=1;o--) sort_sum=sort_sum*(other+o); for (o=space-1;o>=1;o--) sort_sum=sort_sum/o; return sort_sum; }
解题思路:
用数学排序方法,除了N=4是特殊的。
题目说00在一起为无效数,那么我们先算出N位数的数一共有多少个,再减去无效数,主要计算无效数有多少个。
假设输入5 10
先从两个零开始计算,设一个数为11100,那么我们先算出总的排序数,除了开头的1不能动,其他对0进行插空。
。0。0。有C(n+m-1)(m-1),这里n为1的个数,m为space空的个数,得到就是总的排序数。
最后减去不是两个零并列的排列数。010 。 就得到了当两个零并列的排列数count0;
然后根据进制通用公式count0*pow((double)max,N-i)算出当两个零并列 的数有多少个,然后继续循环。
注意事项:
注意other非零数等于1是的情况
参考代码:
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:905 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:622 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1328 |
【偶数求和】 (C语言代码)浏览:583 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:536 |
出圈】指针malloc版浏览:373 |
C二级辅导-进制转换 (C语言代码)浏览:745 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:565 |
1134题解(求分析)浏览:792 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:546 |