整數拆分演算法

Ⅰ C語言 整數拆分問題

比如一個三位數 123
int a,b,c;
c = 123%10 =3
a=123/100 = 1
b = 123/10%10 =2

這樣一個整數123，就拆分成 1,2,3 三個數了。

Ⅱ 如何用C語言拆分整數

將一個整數的各個位分離出來的最簡單方法就是模10，取個位數，直到該變為0。

參考代碼：

#include<stdio.h>
voidmain()
{
intn=0;
scanf("%d",&n);
do{
printf("%d
",n%10);//每次輸出個位
n/=10;//縮小10倍，去除原來的個位。
}while(n);
}

但這整拆分的特點是從後向前輸出每一位數。

如果僅是為了輸出，還想正向輸出每一位數，則可用遞歸函數來解決。（也可以實現逆向輸出）

參考代碼：

#include<stdio.h>
voidsplit_int(intn)
{
	if(n>0)
	{
	//printf("%d
",n%10);//逆向輸出，放開這里，關閉下面的printf().即：先輸出當前個位，再去高位的數
		split_int(n/10);//先去輸出高位的數
		printf("%d
",n%10);//再輸出當前的個位數
	}
}
voidmain()
{
	intn;
	scanf("%d",&n);
	split_int(n);
}

如果想把分離開的數據存儲到數組中，則最簡單的方法是將整數用sprintf()存儲到字元數組中，然後，遍歷數組，逐位取出。

參考代碼：

#include<stdio.h>
voidmain()
{
	intn,i;
	charstr[20];
	scanf("%d",&n);
	sprintf(str,"%d",n);
	for(i=0;str[i];i++)//正向輸出
		printf("%c
",str[i]);
	for(i--;i>=0;i--)//逆向輸出
		printf("%c
",str[i]);
}

Ⅲ java實現整數拆分演算法，例如輸入一個4會輸出4 , 3 1, 2 2, 2 1

importjava.util.Scanner;//輸入的

publicclassABS{//外面建的點java的文件名必須和這個一樣


publicstaticinta[]=newint[12000];

staticvoidp(intn,intindex)//搜索
{

inti;
if(n<=0)//當n為0的時候輸出這種情況
{
System.out.print(a[0]);
for(i=1;i<index;System.out.print("+"+a[i++]));
System.out.print("
");
return;//返回到函數調用的地方
}
for(i=index>0&&(n>=a[index-1])?a[index-1]:n;i>0;i--)
{//如果數組下標大於0且n剩餘的值大於等於上一個的值，那麼i就等於上一個的值，否則i就等於n
a[index]=i;
p(n-i,index+1);//在次調用
}
}

publicstaticvoidmain(String[]args){

Scannerin=newScanner(System.in);//從控制台中讀取輸入數據
intt;
t=in.nextInt();//輸入一個整數
if(t>=10000)
{
System.out.println("你輸入的數據超過1萬，太大咯！！！");
return;
}
p(t,0);
in.close();//關閉輸入
return;
}
}

這個只是可以實現10000 以內的數， 如果想大一點 就把數組開大一點局可以了！

Ⅳ 求演算法：把一個數M分成N個整數．．．

我們要編寫一個函數，這個函數把一個數分為兩個數之和，並且這兩個數的乘積最大，這樣的函數是不是很好編寫，代碼如下：
void f1(int a, int *x,int *y){
*x=a/2;
*y=a-*x;
}
知道為什麼這樣分嗎，原理很簡單：兩個數都最大的時候，乘積才最大。也就是各取一半，如果a是奇數就讓y多1。

要完成把N分為多個數，使其乘積最大，我們就先分為兩個數，然後分別對這兩個數進行各自進行拆分（遞歸調用），直到分開的兩個數乘積比分前小，那就取消這次拆分。

基於以上說明，我們對f1函數進行修改，增加遞歸調用部分：
void f1(int n){
int x,y;
x=n/2;
y=n-x;
if (n>=x*y) printf("%d ",n);
else {f1(x);f1(y);}
}

添加計算乘積m的代碼，以及主程序，完成的如下：

－－－－－－－－－－－－－－－－－
int m;

void f1(int n){
int x,y;
x=n/2;
y=n-x;
if (n>=x*y) {printf("%d ",n);m*=n;}
else {f1(x);f1(y);}
}

main(){
int n;
m=1;
scanf("%d",&n);
f1(n);
printf("\n%d",m);
}
－－－－－－－－－－－－－－－－－
程序在SCO UNIX上運行通過，結果如下：
－－－－－－－－－－－－－－－－－
$ cc a.c
$ a.out
9
4 2 3
24
$ a.out
10
2 3 2 3
36
$ a.out
12
3 3 3 3
81
$

Ⅳ 分解整數

講思路不擅長啊...大體是這樣了:
如15而言,外循環i從1到7,針對每一個i,都計算從它開始的連續和值,等於15了就輸出一行.你還是看下偽代碼吧:
n=15;
for(i=1;i<=n/2;i++)
{
sum=0;
for(j=i;j<=n/2+1;j++)
{
sum+=j;
if(sum==n)
{
for(k=i;k<=j;k++)
printf("%d ",k);
printf("\n");
break;
}
}
}

好吧..我重新研究了下,發現你的數據規模太大了,如果按上面的演算法,效率非常低,改進了演算法,如下:

思路:
如15,有3種情況,一種是2個數字:7,8,一種是3個數字:4,5,6,一種是5個數字:1,2,3,4,5;
我們先求得每種情況的平均值,如情況2的:15/3=5,然後就可以列出4,5,6了.
我們發現,如果是偶數個數字,如2個數字,平均值15/2=7.5,小數部分必然是0.5,這可以想像得到.
而奇數個數字的情況,如3個數字,15/3=5,平均值必然是整數.這也可以想像得到.
如是有以下演算法:
long i,n,sqrtn,first;
scanf("%ld",&n);
sqrtn=(int)sqrt(n*2); //第t行
for(i=2;i<=sqrtn;i++)
{
first=n/i-(i-1)/2;
if((float)n/i-n/i==(i+1.0)/2.0-(i+1)/2 && first>0) //第s行
{
printf("%ld+...+%ld (%ld)",first,first+i-1,i);
}
printf("\n");
}
}

如注釋處,第s行代碼為關鍵代碼(float)n/i-n/i==(i+1.0)/2.0-(i+1)/2即平均值的情況,這里也可以用求余.first>0即所有項必須為正整數.
第t行代碼,連續正整數個數小於sqrt(N*2);這個可以從高斯求和公式推出來.

Ⅵ 整數分解的實際應用

給出兩個大素數，很容易就能將它們兩個相乘。但是，給出它們的乘積，找出它們的因子就顯得不是那麼容易了。這就是許多現代密碼系統的關鍵所在。如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破，包括RSA公鑰演算法和Blum Blum Shub隨機數發生器。
盡管快速分解是攻破這些系統的方法之一，仍然會有其它的不涉及到分解的其它方法。所以情形完全可能變成這樣：整數分解問題仍然是非常困難，這些密碼系統卻是能夠很快攻破。有的密碼系統則能提供更強的保證：如果這些密碼系統被快速破解（即能夠以多項式時間復雜度破解），則可以利用破解這些系統的演算法來快速地（以多項式時間復雜度）分解整數。換句話說，破解這樣的密碼系統不會比整數分解更容易。這樣的密碼系統包括Rabin密碼系統（RSA的一個變體），以及 Blum Blum Shub隨機數發生器。
2005年，作為公共研究一部分的有663個二進制數位之長的RSA-200已經被一種一般用途的方法所分解。
如果一個大的，有n個二進制數位長度的數是兩個差不多大小相等的素數的乘積，還沒有很好的演算法來以多項式時間復雜度分解它。
這就意味著沒有已知演算法可以在O(n)（k為常數）的時間內分解它。但是演算法也是比Θ(e)快的。換句話說，現在我們已知最好的演算法比指數數量級時間要快，比多項式數量級時間要慢。已知最好的漸近線運行時間是普通數域篩選法(GNFS)。時間是：
對於平常的計算機，GNFS是我們已知最好的對付n個二進制數位大素數的方法。不過，對於量子計算機，彼得·肖在1994年發現了一種可以用多項式時間來解決這個問題的演算法。如果大的量子計算機建立起來，這將對密碼學有很重要的意義。這個演算法在時間上只需要O(n)，空間只要O(n)就可以了。 構造出這樣一個演算法只需要2n量子位。2001年，第一個7量子位的量子計算機第一個運行這個演算法，它分解的數是15。

Ⅶ 整數的拆分原理

原理：所謂整數的分拆 ，指將一個正整數表示為若干個正整數的和。

根據是否考慮分拆部分之間的排列順序，我們可以將整數分拆問題分為有序分拆（composition）和無序分拆（partition）。兩者之間的區別如下：

在有序分拆中，考慮分拆部分求和之間的順序。假定

我們稱之為n的無序k拆分，如3的無序k拆分為：3=1+2。這種拆分可以理解為將n個無區別的球分為r份且每份至少有一個球。

一般情況下，無序拆分的個數用 p(n) 表示，則 p(2)=1，p(3)=2，p(4)=4。

在通常情況下，整數分拆是指整數的無序分拆。

整數分拆理論，主要是研究各種類型的分拆函數的性質及其相互關系。早在中世紀，就有關於特殊的整數分拆問題的研究。18世紀40年代，L.歐拉提出了用母函數法（或稱形式冪級數法）研究整數分拆，證明了不少有重要意義的定理，為整數分拆奠定了理論基礎。解析數論中的圓法的引進，使整數分拆理論得到了進一步發展。整數分拆與模函數有密切關系，並在組合數學、群論、概率論、數理統計學及質點物理學等方面都有重要應用。

Ⅷ java實現 整數拆分 希望有個演算法

我給你寫一個，要給分的呦。代碼如下：

import java.util.ArrayList;
import java.util.List;

public class Testxxx {
public void chaifen(int n){
List list = new ArrayList();
chaifendigui(n,list);
}
public void chaifendigui(int n, List list) {
// TODO Auto-generated method stub

for (int i = 1; i <= n; i++) {

System.out.print(i+" ");
if(n>i){
List list2 = new ArrayList();
list2.addAll(list);
list2.add(i);
chaifendigui(n-i,list2);
}else{
System.out.println();
for (int j = 0; j < list.size()-1; j++) {
System.out.print(list.get(j)+" ");
}
}

}
}
public static void main(String[] args) {
Testxxx xx = new Testxxx();
xx.chaifen(10);
}
}

Ⅸ 數學整數拆分法

10，
19，28.，37，46，55，
118，127，135，145，226，235，244，334，
1117，1126，1135，1144，1225，1234，1333，2224，2233，
11116，11125，11134，11224，11233，12223，22222，
111115，111124，111133，111223，112222，
1111114，1111123，1111222，
11111113，11111122，
111111112，
1111111111。
總公42個，枚舉法就這樣，關鍵是寫數字的排列方法不要遺漏不要多寫，其他方法還沒想出來

Ⅹ 把一個正整數n分解成N個正整數的和,求演算法思路，代碼更好！

#include "stdio.h"
#include "string.h"
int t;
int D;
void dd(int s[],int m,int n);
int main()
{
int s[100];
memset(s,0,sizeof(s));
printf("輸入一個正整數:");
scanf("%d",&D);
dd(s,1,D);
}
void dd(int s[],int m,int n)
{
int i,j,k;
i=m;
j=n;
if(i<=j-i)
{
t=t+1;
s[t]=i;
for(k=1;k<=t;k++)
{
printf("%d+",s[k]);
}
printf("%d=%d\n",j-i,D);
dd(s,i,n-i);
t=t-1;
dd(s,i+1,j);
}
}