遞歸演算法分解因數

㈠ 寫一個程序，把一個100以內的自然數分解因數（使用遞歸函數）

呵呵，學習了，本人只會用b語言寫這個，記得當時的關鍵是外部命令要封閉，不能泄露或進入死循環，還有就是知道是100以內的數字，就可以採用窮盡法進行，在首先判斷非質數的情況下分兩步：一是指令循環數字固定，依次為2、3、5、7、11、13、17、18、23、29、31、37、41、43；二是余數0的判定，反正就是循環用上面的固定質數去除，採用兩個循環命令即可，最後的列印格式就簡單了。

㈡ c++/c語言因式分解

【解題思路】
對一個數進行因式分解，可以採用遞歸的辦法，先找出這個數最小的因式，然後再把這個數除以因式，繼續找，直到除到這個數成為質數為止。比如要對60進行因式分解，可以先找到60的最小因式2；然後再把60除以2得到30，接著找30的最小因式得到2；再把30除以2得到15，接著找15的最小因式3；然後再把15除以3得到5；然後5是質數，無法再分解，最終就得到60的因式共有4個，分別是2，2，3，5。而判斷一個數b是不是另一個數a的因式必須符合兩個標准，一是a必須能被b整除；二是b必須是質數。根據以上思路，代碼如下：（為了簡化程序，這里把判斷是否質數和分解因式都分別做成一個獨立的函數）
【程序代碼】
#include<iostream>//控制台操作頭文件
#include<math.h>//數學函數頭文件

//---------------
boolSS(inta)//質數判斷函數(質數返回1,否則0)
{if(a<2)returnfalse;//小於2的數都不是質數,返回0
if(a==2)returntrue;//2是特殊的質數
inti,n=(int)sqrt(a);//n是除數,開方可以減少檢測個數
for(i=2;i<=n;i++)//逐個檢測能不能被整除
if(a%i==0)returnfalse;//如果能被整除說明不是質數,返回0;returntrue;}//檢測完了還沒可以被整除的數,返回1
//---------------
voidYs(ints[],inta)//因式分解的遞歸函數
/*s是存放各個因式的數組,其中s[0]為因式個數,a是要分解因素的數字*/
{inti,n;//循環變數和因式個數
n=++s[0];//每遞歸調用一次因式個數增加1
if(SS(a)){s[n]=a;return;}//如果a是質數,沒有因式,函數結束
for(i=2;i<a;i++)//由小到大找出a的第一個因式
if(SS(i)&&a%i==0)break;//如果i是質數並且a可以被i整除
s[n]=i;//保存這個因式
Ys(s,a/i);}//遞歸調用函數繼續分解下個因式
//---------------
intmain()//主函數
{inta,i;//整型變數
intS[100];//用於存放因式的數組

for(;;)//弄一個無窮循環
{printf("請輸入一個正整數(-1結束):");//顯示提示信息
scanf("%d",&a);//從鍵盤輸入一個整數
if(a==-1)break;//如果輸入-1退出循環
if(a<0)continue;//如果輸入不是正數重新輸入
S[0]=0;//因式個數清零
Ys(S,a);//調用函數分解因式
printf("%d共有%d個因式,分別是:",a,S[0]);//顯示因式個數
for(i=1;i<=S[0];i++)printf("%d",S[i]);//顯示各個因式
printf("

");}//顯示完所有因式換行
printf("
");//結束程序前再空一行
system("PAUSE");//屏幕暫停查看顯示結果
return0;}//結束程序

【運行結果】
以上程序在DEVC++上運行通過。

截圖如下：

㈢ 用java編程 將一個正整數分解質因數。例如：輸入90,列印出90=2*3*3*5。

將一個正整數分解質因數。例如:輸入60；列印出2*3*5*2

演算法實現構思:

1、用Scanner實現輸入一個正整數n

2、用一個for循環遍歷一個從 k=2開始查找到k<=n的數

3、如果 n%k==0的時候，輸出k的值

4、然後把n的值遞歸一下，即 n=n/k

5、這個時候要把for循環重新執行，即再定義k=2

下面是實現代碼：

上面是後來整理的構思以及代碼實現，一開始拿到這個題目，就立馬去做了，可是馬上掉進了各種各樣的坑，我覺得以後做演算法題先把做題思路想好，從部分到整體，不然一道簡單的演算法題就要耗掉很多時間。

㈣ 遞歸演算法是什麼

遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。

遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。

計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。

㈤ 歸並演算法中的遞歸分解，不太理解兩層遞歸。求解釋

這個很好理解，不要把他想的太復雜。
MergerSort(int[] v, int first, int last)方法本身的含義就是，在數組v從first到last的范圍內進行排序。
具體排序方法，在fist和last取一個中間數就是mid,然後從first到mid在進行排序MergerSort(v, first, mid)，mid到last再排序 MergerSort(v, mid, last);，排序完畢把數組組合起來就可以了。

㈥ 用Java對正整數分解質因數

因為你沒有加結束的條件
在函數中第一行加
if(x==0)//x==0該子問題結束
return;
遞歸兩個必須元素：
（1）遞歸終止的條件
（2）分解問題

㈦ 遞歸法分解正整數n的質因數

#include<iostream>

using namespace std;

int f(int x)//質數判斷函數

{

if(x<2)

return 0;

for(int i=2;i*i<=x;i++)

if(x%i==0)

return 0;

return 1;

}

void dfs(int &x,int n)//遞歸求解

{

if(x<=1)//遞歸結束

return;

for(int i=2;i<n;i++)

{

if(f(i)&&x%i==0)//能整除且是質數

{

cout<<i<<" ";//輸出質因子

dfs(x/=i,n);//x/=i:將當前質因子除去,遞歸尋找下一個質因子

}

}

}

int main() {

int n,x;

cin>>n;

x=n;

dfs(x,n);//x記錄質因子(一直在變)，n就是要分解的數 (一直不變)

return 0;

}

㈧ 關於遞歸的問題，請C語言牛人回答

這是利用輾轉相除法求最大公約數
看看資料
輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至3000年前。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
證明：
設兩數為a、b(b＜a)，求它們最大公約數(a、b)的步驟如下：用b除a，得a＝bq......r 1(0≤r)。若r1=0，則(a，b)＝b；若r1≠0，則再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，則(a，b)＝r1，若r2≠0，則繼續用r2除r1,……如此下去，直到能整除為止。其最後一個非零餘數即為(a，b)。
[編輯] 演算法
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余數, 則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法是：
1. a ÷ b，令r為所得余數（0≤r＜b）
若 r = 0，演算法結束；b 即為答案。
2. 互換：置 a←b，b←r，並返回第一步。
[編輯] 虛擬碼
這個演算法可以用遞歸寫成如下:
function gcd(a, b) {
if b<>0
return gcd(b, a mod b);
else
return a;
}
//c語言實現 輾轉相除法（遞歸）
#include <stdio.h>
int Euclid(int a,int b);
int main(void)
{
int a,b;
printf("Enter the two figures:");
scanf("%d %d",&a,&b);
printf("gcd:%d\n",Euclid(a,b));
return 0;
}
int Euclid(int a,int b)
{
if(a % b == 0)
return b;
else
return Euclid(b,a%b);
}
或純使用循環:
function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
pascal代碼（遞歸）
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
其中「a mod b」是指取 a ÷ b 的余數。
例如，123456 和 7890 的最大公因子是 6, 這可由下列步驟看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0
只要可計算余數都可用輾轉相除法來求最大公因子。這包括多項式、復整數及所有歐幾里德定義域（Euclidean domain）。
輾轉相除法的運算速度為 O(n2)，其中 n 為輸入數值的位數。
輾轉相除法原理及其詳細證明如下:
「輾轉相除法」又叫做「歐幾里得演算法」，是公元前 300 年左右的希臘數學家歐幾里得在他的著作《幾何原本》提出的。利用這個方法，可以較快地求出兩個自然數的最大公因數，即gcd 或叫做HCF 。
最大公約數（greatest common divisor，簡寫為gcd；或highest common factor，簡寫為hcf)
所謂最大公因數，是指幾個數的共有的因數之中最大的一個，例如 8 和 12 的最大公因數是 4，記作gcd(8,12)=4。
在介紹這個方法之前，先說明整除性的一些特點（下文的所有數都是正整數，不再重覆），我們可以這樣給出整除性的定義：
對於二個自然數a和b，若存在正整數q，使a=bq，則a能被b整除，b為a的因子，a為b的倍數。
如果a能被c整除，並且b也能被c整除，則c為a、b的公因數（公有因數）。
由此我們可以得出以下推論：
推論1、如果a能被b整除（a=qb），若k為正整數，則ka也能被b整除（ka=kqb）
推論2、如果a能被c整除（a=hc），b也能被c整除（b=tc），則(a±b)也能被c整除
因為：將二式相加：a+b=hc+tc=(h+t)c 同理二式相減：a－b=hc－tc=(h－t)c
所以：(a±b)也能被c整除
推論3、如果a能被b整除（a=qb），b也能被a整除（b=ta），則a=b
因為：a=qb b=ta a=qta qt=1 因為q、t均為正整數，所以t=q=1
所以：a=b
輾轉相除法是用來計算兩個數的最大公因數，在數值很大時尤其有用，而且應用在電腦程式上也十分簡單。其理論如下:
如果 q 和 r 是 m 除以 n 的商及余數，即 m=nq+r，則 gcd(m,n)=gcd(n,r)。
證明是這樣的: 設 a=gcd(m,n)，b=gcd(n,r)
證明：
∵a為m,n的最大公約數，
∴m能被a整除，且n也能被a整除，
∴由推論1得：qn也能被a整除，
∴ 由推論2得：m-qn也能被a整除，
又 ∵m-qn=r，
∴r也能被a整除，即a為n和r的公約數（注意：還不是最大公約數）
∵b為n和r的最大公約數，a為n和r的公約數
∴a≤b，
同理
∵b為n, r的最大公約數，
∴n能被b整除，且r也能被b整除，
∴由推論1得：qn也能被b整除，
∴由推論2得：qn+r也能被b整除，
又∵m=qn+r，
∴m也能被b整除，即b為m和n的公約數，（注意：還不是最大公約數）
∵a為m,n的最大公約數，b為m和n的公約數，
∴b≤a，
由以上可知：
a≤b與b≤a同時成立，
故可得
a=b，
證畢。
例如計算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39
若還不理解可以加我好友我們探討探討

㈨ 用JAVA中遞歸思想編寫程序：分解質因數例如90=2×3×3×5

按照你的要求編寫的Java程序如下：

importjava.util.Scanner;
publicclassCCT{
publicstaticvoidf(intn,intm){
inti=2;
if(n<2)return;
while(!(n%i==0)){
i++;
}
if(m==1)System.out.print(i);
elseSystem.out.print("*"+i);
f(n/i,m-1);
return;
}
publicstaticvoidmain(String[]args){
Scannersc=newScanner(System.in);
intn=sc.nextInt();
System.out.print(n+"=");
f(n,1);
System.out.println();
}
}

運行結果：

90
90=2*3*3*5

㈩ java中遞歸演算法是什麼怎麼算的

一、遞歸演算法基本思路：

Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

二、遞歸演算法解決問題的特點：

【1】遞歸就是方法里調用自身。

【2】在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代碼執行流程圖如下：

此程序中n=5就是程序的出口。