主题：(求助)狗狗的城堡
simon52
[专家分：0] 发布于 2006-05-06 12:49:00
Description
终于到小岛了，小岛上绿茵遍地，风景如画，大家都兴奋的到处去玩了，只有狗狗一个人趴在地上。原来狗狗发现了一堆一样大小的砖头，狗狗很喜欢玩搭积木，就想在小岛上建一个漂亮的城堡。不过首先狗狗想为城堡建一个标志建筑，为了节约砖头，狗狗决定这个建筑的厚度只要一层。那么，请你帮狗狗想想，N块砖头可以搭多少种不同样式的建筑呢？注意： 建筑必须是连续的。
Input
输入砖头的数量N(2<=n<=20)
Output
输出所有样式的数字表示。
1代表一块砖，2代表2块叠加，依次类推
1 1 1 1代表4块砖头连续摆放
Sample Input
4
Sample Output
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4
这个题目怎么解决啊，麻烦高手用C++写一个
回复列表 （共4个回复）
沙发
bixuan [专家分：100] 发布于 2006-05-07 20:43:00
还没学C++ ,用C编的,不过我想C跟C++差不多吧,自己再换成C++
# include<stdio.h>
void main()
{
void plus(int,int *p);
int a[20],n,i;
scanf(“%d”,&n);
printf(“%d\n”,n);
for(i=1;i<=n-1;i++)
{
a[0]=i; a[1]=n-a[0];
plus(1,a);
}
}
void plus(int i,int *p)
{
int m,k;
for(m=0;m<=i;m++)
printf("%3d",p[m]);
printf("\n");
k=p[i];
for (m=1;m<=p[i]-1;m++)
{
p[i++]=m; p[i]=k-p[i-1];
plus(i,p);
}
}
在Turbo C&C++ 3.0 编译通过
如果输入的n超过20,将a[20]里的20改成你想要输入的最大数
板凳
simon52 [专家分：0] 发布于 2006-05-31 19:01:00
不行啊，你这个算法不行，每次递归后只是往前加一，从示例中的答案来看就不行
3 楼
gotowqj [专家分：10] 发布于 2006-06-13 11:37:00
#include<iostream>
using namespace std;
int way[20];
int sum=0;
int step=0;
void compute_way(int n);
int main()
{
int n;
while(cin>>n)
{
compute_way(n);
}
return 0;
}
void compute_way(int n)
{
if(sum==n)
{
for(int i=0;i<step;i++)
cout<<way[i]<<" ";
cout<<endl;
return ;
}
if(sum>n)
{
return ;
}
if(sum<n)
{
for(int j=1;j<=n;j++)
{
if((sum+j)<=n)
{
sum=sum+j;
way[step]=j;
step++;
compute_way(n);
sum=sum-j;
step--;
}
}
}
}
递归回溯法
4 楼
tcdkz [专家分：210] 发布于 2006-08-15 15:28:00
我的pascal程序:
program ex;
var
n:integer;
a:array[1..18]of integer;
procedure f(m,k:integer);
var
i,j:integer;
begin
if m>=1 then
for i:=1 to m do
begin
a[k]:=i;
f(m-i,k+1);
end
else begin
for j:=1 to k-2 do write(a[j],' ');
writeln(a[k-1]);
end;
end;
begin
readln(n);
f(n,1);
end.
我来回复
您所在位置：