文章目錄
- python_階乘遞歸求解/尾遞歸形式/字典形式求解
階乘分解(素數因子)
探索版
/*問題D：
題目描述
輸入正整數n （2<n<100），把階乘n! =l*2*3x...xn分解成素因子相乘的形式，輸出各個素數（2、3、 5......）的指數。
例如825=3*5以*11應表示成（0、1、2、0、1）,表示分别由0、1、2、0、1個2、3、
5、7、11。要求你的程式在輸出時忽略比正整數n的最大 素因子 更大的素數，否則會導緻末尾有無窮多個 0。
輸入
輸入正整數n （2<n<100）［多組測試資料］
輸出
n!=（—個空格）a1（—個空格）a2（—個空格）a3...
［a1,a2,a3等數字為分解後素數（2、3、5......）的指數，輸出時忽略大于最大素因子的素數的指數0。］
樣例輸入
5
53
樣例輸出
5!= 3 1 1
53!= 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int is_prime(int i)
{
if (i == 1 || i == 0)
{
return 0;
}
for (int j = 2; j*j < i+1; j++)
{
if (i % j == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int n;
int cnt = 0;
int prime[2][100] = { 0 };/*n<=100;用{0}可以将二維數組裡的元素都初始化為0;
prime[0][100]儲存質數清單;
prime[1][100]儲存計數情況,各個元素充當各個質數的計數器*/
/*填充質數清單*/
for (int i = 2, j = 0; i < 100; i++)
{
if (is_prime(i))
{
prime[0][j++] = i;
}
}
/*處理多組輸入:*/
while (scanf("%d", &n) != EOF)
{
/*每組測試資料開始前初始化計數器.*/
for (int j = 0; j < 100;j++)
{
prime[1][j] = 0;
}
int bak = 0;/*back-up 備份.*/
/*階乘的各個因子分别進行質數因子拆分,使得問題規模分攤在各相似的子問題上*/
for (int i = 2; i <= n;i++)
{/*eg.i = 100時:*/
bak = i;/*輔助變量很重要;處理階乘因子i*/
for (int j = 0; bak >=2;)
{
if (bak % prime[0][j] == 0)/*bak不要寫成i,在這gg了好幾回*/
{
/*同一個質數的屬性*/
bak = bak / prime[0][j];
prime[1][j]++;
}
else
{
j++;
}
}//for
}//for
/*列印*/
for (int i = 0; prime[0][i] <= n && prime[0][i] > 0 && i < 100;/*僅第一個條件還不夠,無法處理99之類的大數;大于n的素數必定會出現在n!的因子中,它們比>=1(因為它們質數還不可以被分解,哪些非1(>1)的是某些合數因子被分解為對應質因子的結果.;i<100是為了保證不列印數組越界後的亂七八糟的數*/
i++)
{
printf("%d ", prime[1][i]);
}
printf("\n"); }
}
/*彩蛋*/
/*int s = 1; long long 是_int64 */
///*這種做法的弊端是有時long long 都難以裝下(規模和大的時候)*/
//for (int i = 1; i <= n; i++)
//{
// s *= i;
//}*/
//for (int i = 2; s > 0;)
//{
// if (i > bak)
// {
// break;
// }
// if (s % i == 0 && is_prime(i) )
// {
// s /= i;
// cnt++;
// }
// else
// {
// if (is_prime(i))
// {
// printf("%d ", cnt);
// }
// cnt = 0;
// i++;
// }
//}//for
AC版:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isprime(int n)
{
if(n == 1 || n == 0)
{
return 0;
}
else
{
for(int i = 2;i*i<n+1;i++)
{
if(n%i == 0)
{
return 0;
}
}
}
return 1;
}//dui
int main()
{
int prime[2][100] = {0};
int i = 0,j = 0 ;
for(i = 0;i<100;i++)
{
if(isprime(i))
{
prime[0][j++] = i;
}
}//dui
int n = 0;
while(scanf("%d",&n) != EOF)
{
for(i = 0;i<100;i++)
{
prime[1][i] = 0;
}//dui
for(int i = 2 ;i<=n;i++)
{
int bak = i;
for(int k = 0;bak>1;)
{
if(bak%prime[0][k]== 0)
{
bak = bak/prime[0][k];
prime[1][k] ++;
}
else
{
k++;
}
}//for
}//for
printf("%d!= ",n);
for(int i = 0;prime[0][i]<=n && prime[1][i] >0;i++)
{
printf("%d",prime[1][i]);
if(prime[1][i+1]>0)//格式錯誤的處理(最後的空格不要)
{
printf(" ");
}
}
printf("\n");
}//while
}
python_階乘遞歸求解/尾遞歸形式/字典形式求解
def factorial(n):
"""傳統遞歸方式編寫計算階乘的函數
Parameters
----------
n : int
速度較慢,譬如(n=100)
Returns
-------
計算結果
"""
if n == 0:
return 1
return n * factorial(n - 1)
def fact_iter(num, product=1):
"""尾遞歸的形式實作階乘
Parameters
----------
num : int
表示需要計算的階乘的數
同時表征遞歸出口(運算次數)
product : int
累計計算結果,最終在遞歸出口傳回
在本調用的執行過程中,後面的函數調用傳入的參數累計了上一次調用的計算結果
Returns
-------
int
計算結果
"""
# 定義遞歸出口
if num == 1:
return product
# num * product是計算關鍵
# num-1是通往出口的關鍵
return fact_iter(num - 1, num * product)
def factorail(n):
return fact_iter(n, 1)
print(factorial(100))
factorial_d=[1]
def factorial_speed(n):
"""fast factorial
Parameters
----------
n : int
需要計算階乘的整數
Returns
-------
int
calculate result
"""
for n in range(1,n+1):
factorial_d.append( n * factorial_d[n - 1])
return factorial_d[n]
if __name__=="__main__":
res=factorial(100)
print("res1:",res)
res=factorial_speed(50)
print("res2:",res)
![[轉]九大排序算法——C語言實作及詳解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)