递归算法分解因数

㈠ 写一个程序，把一个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就是程序的出口。