求整数的各个组合之和(栈和队列)
时间: 1ms 内存:1000M
描述:
题目:输入两个整数 m 和n,从数列1,2,3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
输入:
输入:6
输出:
输出:
6
5 1
4 2
3 2 1
示例输入:
6
示例输出:
6
5 1
4 2
3 2 1
提示:
参考答案(内存最优[752]):
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SEN 100
struct sqstack
{
char *base;
char *top;
int size;
};
struct sqstack *initEmptyStack() /*构建空輚*/
{
struct sqstack *p;
p=(struct sqstack *)malloc(sizeof(struct sqstack));
if(p!=NULL)
{
p->base=(char *)malloc(sizeof(struct sqstack)*SEN);
if(p->base!=NULL)
{
p->top=p->base;
p->size=SEN;
return p;
}
}
else
free(p);
return NULL;
}
int push(struct sqstack *p,int a) /*入栈*/
{
*p->top++=a;
return 0;
}
int gettop(struct sqstack *p) /*取栈顶元素*/
{
if(p->base!=p->top)
return *(p->top-1);
return 0;
}
int pop(struct sqstack *p) /*出栈*/
{
return *(--p->top);
}
int main()
{
struct sqstack *p1,*p2,*p3;
int m,t=1,a,sum,n;
scanf("%d",&m);
p1=initEmptyStack();
p2=initEmptyStack();
p3=initEmptyStack();
printf("%d\n\n",m);
n=m;
m--;
while(m--)
{
sum=0;
t=1;
do{
push(p1,t);
t++;
}while(t<=m+1);
while(p1->base!=p1->top)
{
a=pop(p1);
sum+=a;
if(sum>n)
sum-=a;
else if(sum==n)
{
while(p2->base!=p2->top)
push(p3,pop(p2));
while(p3->base!=p3->top)
printf("%d ",pop(p3));
printf("%d\n\n",a);
sum-=a;
}
else
push(p2,a);
}
while(p2->base!=p2->top)
pop(p2);
}
return 0;
}
参考答案(时间最优[0]):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int length;
void ff(int n,int m,int *flag)
{
if(n < 1 || m < 1)return;
if(n > m)n = m;
if(n == m)
{if(n!=length)
printf("\n");
flag[n-1] = 1;
for(int i=length-1,j=0; i>=0; i--)
if(flag[i] == 1)
{
printf(j==0?"%d":" %d",i+1);
j=1;
}
printf("\n");
flag[n-1] = 0;
}
flag[n-1] = 1;
ff(n-1,m-n,flag);
flag[n-1] = 0;
ff(n-1,m,flag);
}
int main()
{
int m;
scanf("%d",&m);
length=m;
int *flag = (int*)malloc(sizeof(int)*m);
ff(m,m,flag);
free(flag);
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。