程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 編程之美:不要被階乘嚇倒

編程之美:不要被階乘嚇倒

編輯:C++入門知識

問題1描述:

給定整數N,N求N!末尾有幾個0。例如N=10,N!=3628800,N!末尾有兩個0

分析:

一、將N!分解質因數,N!=(2^x)*(3^y)*(5^z)......,由於10=2*5,所以問題也就是求M=min(x,z),容易看出x大於等於z,所以也就是求z

#include 
 
int main(){  
    int N=10;
	int ret=0;
	for(int i=1;i<=N;i++){
		int j=i;
		while(j%5==0){
			ret++;
			j/=5;
		}
	}
	printf("%d\n",ret);
    return 0;  
}  

二、利用公式z=[N/5]+[N/5^2]+[N/5^3]+......

#include 
 
int main(){  
    int N=10;
	int ret=0;
	while(N){
		ret+=N/5;
		N/=5;
	}
	printf("%d\n",ret);
    return 0;  
}  

問題2描述:

求N!的二進制表示中最低位1的位置

分析:

問題2與問題1的區別只是進制上的不同,對於問題1,答案其實就是N!含有多少個10,那麼對於問題2答案就是N!含有多少個2了。

一、利用公式:N/2+N/4+N/16+......

#include 
 
int main(){  
    int N=10;
	int ret=0;
	while(N){
		N>>=1;
		ret+=N;
	}
	printf("%d\n",ret);
    return 0;  
}  

二、對N/2+N/4+N/16+......發現,假設N=11011,

即:1101+110+11+1=(1000+100+1)+(100+10)+(10+1)+1

=(1000+100+10+1)+(100+10+1)+1=1111+111+1

=(10000-1)+(1000-1)+(10-1)+(1-1)=11011-(N二進制表示中1的個數)

#include 
 
int main(){  
    int N=10;
	int ret=0,t=N;
	while(t){
		t&=(t-1);
		ret++;
	}
	printf("%d\n",N-ret);
    return 0;  
}  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved