K-进制数 （利用二进制数抽象化处理）（C语言代码）

解题思路:

这是第一次解法，然而当K值很大时（k>2）,数的基数将会非常大，会报超时，所有效率将非常低，故做了优化，

改成对二进制数的遍历，问题解决

#include<stdio.h>
int main(){
	int i,j,d;
	int n,k;
	long num=0,num1=0;
	int s[20]={1};
	scanf("%d%d",&n,&k);
	while(s[0]!=0){
		int flag1=0;
		for(i=0;i<n-1;i++)
		if(s[i]==0&&s[i+1]==0){
		 flag1++;
		}
		if(flag1==0) num++;
		else if(flag1!=0) num1++;	
		int flag=1;	d=n-1;
		while(flag==1){ 	//如果d位上变成0，则进位加1 
			flag=0;
			s[d]=(s[d]+1)%k;    //对K进制进行遍历
			if(s[d]==0){
				d--;flag=1;
			}
		}
	}
	printf("%d",num);
	return 0;
}

在一个N位K进制数中，每一位数无非两种情况：
   1.为0;  

    2.不为0
 故在第二次代码中，先遍历一次n位的二进制数，表示出数字0的分布情况，统计出非0的个数i,然后每种分
布情况的无效数的个数即为 knum=(k-1)^i; 统计完所有的knum，即为所有无效数字的个数

最后：        
           所有有效数的个数 = 所有不同的N位K进制数的个数 - 无效数字的个数
参考代码:

#include<stdio.h>
int main(){
	int i,j,d;
	int n,k,sum=0;
	long num,num1=0,num2=1;
	int s[20]={1};
	scanf("%d%d",&n,&k);
	while(s[0]!=0){
		int flag1=0;
		for(i=0;i<n-1;i++)
		if(s[i]==0&&s[i+1]==0){
		 flag1++;
		}
		long knum=1;
		if(flag1!=0) 	//统计二进制数无效的个数
		for(i=0;i<n;i++)
		if(s[i]!=0) knum*=k-1;
		if(flag1!=0)	num1+=knum;	//当无效时才加上无效个数 
		int flag=1;	d=n-1;
		while(flag==1){ 	//如果d位上变成0，则进位加1 
			flag=0;
			s[d]=(s[d]+1)%2;    //改成对2进制进行遍历
			if(s[d]==0){
				d--;flag=1;
			}
		}
	}
	for(i=1;i<=n;i++){		//统计出有多少个不同的数
		num=k-1; 
		for(j=1;j<i;j++){
			num*=k;
		}
		sum+=num;
	}
	for(i=1;i<n;i++)	//统计1~1000...0(n位)有多少不同的数 
		num2*=k;
	printf("%d",sum-num2-num1+1);
	return 0;
}