整数拆分算法

Ⅰ 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);
}
}