189 8069 5689

整数划分问题代码java 整数划分问题算法

整数分划问题

设二元函数 f( n , p )为满足以下条件的分划数:

站在用户的角度思考问题,与客户深入沟通,找到江山网站设计与江山网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:网站设计、做网站、企业官网、英文网站、手机端网站、网站推广、域名注册网站空间、企业邮箱。业务覆盖江山地区。

1. p = n1 = n2 = ... = nk

2. n1 + n2 + ... + nk = n

按以下方法可以求出f( n , p )的递推关系式:

当n1 = p 时,

应有 n2 + ... + nk = n - p ,

且 p = n2 = ... = nk

有 f( n-p , p )种分划;

当n1 = p + 1 时,

应有 n2 + ... + nk = n - p - 1 ,

且 p+1 = n2 = ... = nk

有 f( n-p-1 , p+1 )种分划;

同理

n1 = p + 2 时有 f( n-p-2 , p+2 )种分划;

n1 = p + i 时有 f( n-p-i , p+i )种分划;

最后,n1 = n ,有 1 种分划。

所以 f( n , p ) = f(n-p , p) + f(n-p-1 , p+1) + ..

.. + f(n-p-i , p+i) + ... + f(1 , n-1) + 1

另外,在这个函数中,当 2*pn 时,也就是 n1 大于 n/2 时,

显然可以看出 f=0,因为这样的分划不存在。

所以上式可以化简成

f( n , p ) = f(n-p , p) + f(n-p-1 , p+1) + ..

.. + f(n-p-i , p+i) + ... + f( [n/2] , n-[n/2]) + 1

所以你的题目就是求f(n,1)的值

f(n,1)=f(n-1,1) + f(n-2,2) + .. + f([n/2],n-[n/2]) +1

(把[ ]当作上取整)

用递归实现上面说的那个函数,然后把你指定的n和1作参数传递给它就OK了。

哦对了,递归出口是f(1,1)=1,这个由题意和函数的定义很容易得到。

ps,这个函数似乎可能应该好象可以转化成非递归型的,不过我懒得继续再想了.....对小于80的数我的机子都用不到1秒..

另外,你的题目里是否应该n=6时输出11 ?

PASCAL我不会,反正这数学模型没问题,转化成语言应该是你自己的事吧.

关于java整数划分并求出划分的个数的问题,有代码,能输出整数的划分,但输出的划分个数不对。

import java.util.Scanner;

public class numberDiv {

// private static final huafen numberrDiv = null;

// static int d[]=new int[32];

public static void main(String[] args) {

System.out.println("请输入的整数:");

Scanner sc = new Scanner(System.in);

int number = sc.nextInt();

int num = numberDiv.Division(number, number, "");

System.out.println("num=" + num);

}

public static int Division(int m, int n, String str) {

if ((m = 0) || (n = 0))

return 0;

if ((m == 1) || (n == 1)) {

System.out.print(str);

for (int i = 1; i  m; i++) {

System.out.print("1+");

}

System.out.println("1");

return 1;

}

if (n == m) {

System.out.println(str + m);

return 1 + numberDiv.Division(m, n - 1, str);

}

if (m  n) {

int n1 = numberDiv.Division(m - n, n, str + n + "+");

int n2 = numberDiv.Division(m, n - 1, str);

return n1 + n2;

}

return numberDiv.Division(m, m, str);

}

}

Division方法返回分解的个数,所以numberDiv类不需要再定义成员变量static int num=0;。

Division方法中if ((m == 1) || (n == 1))成立时,本次是一个分解,并且不需要再递归分解,所以返回1。

Division方法中if (n == m)成立时,本次是一个分解,且需要递归分解,所以返回1+递归分解个数。

Division方法中if (m n)成立时,返回两个递归分解的个数之和。

Division方法中最后代码即为m  n,直接返回递归分解的个数。

C语言 递归算法 整数划分问题

#includestdio.h

int stack[100];

int top;

int total,n;

void dfs(int index)

{

int i;

if(total==n)

{

printf("%d=",n);

for(i=top-1;i0;i--)

printf("%d+",stack[i]);

printf("%d\n",stack[0]);

}

if(totaln )

return ;

for(i=n-1;i=index;i--)

{

total+=i;

stack[top++]=i;

dfs(i);

total-=i;

stack[--top];

}

}

void main()

{

while(scanf("%d",n)!=EOF)

{

top=0;

total=0;

dfs(1);

}

}

求一道java程序设计题(整数划分)

这个可以用递归来实现。。。。。代码如下。。。还是想了很久弄出来的。。。。已经测试了的。。。希望能帮到你。。。

import

java.util.Scanner;

public

class

Test

{

public

static

void

huafenD(int

oldData,int

j,

int

n,StringBuffer

result){

StringBuffer

r

=

new

StringBuffer(result);

for(

int

i

=

j;i=n;i++){

if(i==ni!=oldData)

{

result.append(i);

System.out.println(result.toString());

result

=

new

StringBuffer(r);

}

else

if(i!=oldData){

result.append(i);

result.append("+");

huafenD(oldData,i,n-i,result);

result

=

new

StringBuffer(r);

}

}

}

public

static

void

main(String

args[])

{

Scanner

in

=

new

Scanner(System.in);

System.out.println("请输入一个整数(1-10)");

int

data

=

in.nextInt();

while(data1||data10){

System.out.println("您的输入

不符合要求,请重新输入");

data

=

in.nextInt();

}

if(data==1)System.out.println("无需划分");

else

{

StringBuffer

sb

=

new

StringBuffer();

huafenD(data,1,data,sb);

}

}

}

运行结果示例:

请输入一个整数(1-10)

6

1+1+1+1+1+1

1+1+1+1+2

1+1+1+3

1+1+2+2

1+1+4

1+2+3

1+5

2+2+2

2+4

3+3


网站名称:整数划分问题代码java 整数划分问题算法
链接URL:http://jkwzsj.com/article/ddgcsco.html

其他资讯