階乗に関する問題

2031 ワード

1、整数Nの階乗を求める.
より小さい数Nの乗算は、基本データ型で表すことができる.ただし、Nが大きい場合、得られる結果は、基本データ型が表す範囲を超えてしまう.したがって、配列を使用して最終的な結果を保存することを考慮します.
#include <stdio.h>

#define N 200     //     

int main()
{
	int i, j, n, r, s;
	int a[N] = {0};     //       
	
	scanf("%d", &n);
	for(i = 1, a[0] = 1; i <= n; i++)
	{
		r = 0;         //   
		for(j = 0; j < N; j++)
		{
			s = a[j] * i + r;
			a[j] = s % 10;
			r = s / 10;
		}
	}
	for(i = N - 1; i >= 0 && a[i] == 0; i--); //            
	while(i >= 0)  //       
	{
		printf("%d", a[i]);
		i--;
	}
	printf("
"); return 0; }

2、Nの階乗末尾0の個数Mを求める
与えられたNの場合、乗算を先に計算してから最後の0の個数を計算すると、メモリオーバーフローが発生する可能性があります.実はN!素因数分解を行うと,解決策を見つけることができる.
N! = 1 * 2 *  ······ * N = (2^X) * (3^Y) * (5^Z) * ······
上式からMの大きさはXとZのみに関係していることが分かるが,2*5=10であるためM=min(X,Z)である.また1~Nで2で割り切れる数は5で割り切れる数より多く,最終的な結果はM=Zである.これにより、実装プログラムを書くのは難しくありません.
#include <stdio.h>

int main()
{
	int i, j, n, res = 0;
	
	scanf("%d", &n);

	for(i = 1; i <= n; i++)
	{
		j = i;
		while(j % 5 == 0)
		{
			res++;
			j /= 5;
		}
	}

	printf("%d
", res); return 0; }

3、Nを求める!のバイナリ表示で最下位1の位置がNを求めれば!次にバイナリに変換して最低ビット1の位置を求め,効率が低い.1つの数をバイナリに変換すると、この数が偶数であれば、バイナリ表現に変換された最後のビットは0になることを知っています.この数が奇数であれば、バイナリ表現に変換された最後のビットは1になります.だからこの問題はNを求めることに相当します!素因数2を含む個数に1を加える.
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int i, j, n, res;
	while(scanf("%d", &n))
	{
		res = 1;
		for(i = n; i > 0; i--) // 1~n     2   
		{
			j = i;
			while(j % 2 == 0)
			{
				res++;
				j /= 2;
			}
		}
		printf("%d
", res); } return 0; }

プログラム2
#include <stdio.h>

int main()
{
	int N, C;
	while(scanf("%d", &N))
	{
		C = 1;
		while(N)
		{
			N >>= 1;
			C += N;
		}
		printf("%d
", C); } return 0; }

』』』は本を尽くしたほうが本がないほうがましだ.