以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  中科大考研算法题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=19190)


--  作者:tangdragon
--  发布时间:6/3/2005 1:19:00 PM

--  中科大考研算法题
请教各位:
要求用递归解法.
    对于正整数n, 输出和为n且满足以下限制条件的所有正整数的和式, 组成和式的数字自左至右构成一个非递增的序列. 如n = 4, 输出
    4 = 4
    4 = 3 + 1
    4 = 2 + 2
    4 = 2 + 1 + 1
    4 = 1 + 1 + 1 + 1
要求用递归解法.
--  作者:asadafag
--  发布时间:6/3/2005 4:54:00 PM

--  
汗……这不是小学竞赛题……

--  作者:tangdragon
--  发布时间:6/3/2005 11:13:00 PM

--  
做出来再说话不迟
--  作者:tangdragon
--  发布时间:6/3/2005 11:30:00 PM

--  
终于调试出来了.
--  作者:asadafag
--  发布时间:6/6/2005 3:01:00 PM

--  
为堵楼主之口,随便写了一个……
#include <stdio.h>

int ns[20],sp;
int n0,d,d0;
void search(int n,int m)
{
  int i;
  if(n<0||m==0)return;
  if(n==0)
  {
    if(d0==d)return;
    d0=d;
    printf("%d = %d",n0,ns[0]);
    for(i=1;i<sp;i++)
      printf(" + %d",ns[i]);
    printf("\n");
    return;
  }
  ns[sp++]=m;d++;search(n-m,m);sp--;
  search(n,m-1);
}

int main()
{
  scanf("%d",&n0);
  sp=0;d0=d=0;
  search(n0,n0);
  return 0;
}


--  作者:tangdragon
--  发布时间:6/6/2005 9:14:00 PM

--  
不必动气,多谢指教!
--  作者:tianmeng
--  发布时间:6/8/2005 10:32:00 AM

--  
算法有误

--  作者:sunmansunman
--  发布时间:8/23/2005 11:00:00 PM

--  
#include "stdafx.h"
#include <iostream>

using namespace std;

void Gen(int array[], int N, int index)
{
 for(int i = 0; i < index; ++i)
 {
  cout << array[i] << ends;
 }
 cout << endl; 

 for(int i = 0; i < index; ++i)
 {
  if(array[i] > 1 && array[i] > array[i+1])
  {
   array[i] = array[i] - 1;
   long j = i+1;
   while(array[j]+1 > array[i])
    ++j;
   array[j] += 1;

   Gen(array, N, j+1);
  }
 }
}

int _tmain(int argc, _TCHAR* argv[])
{
 int n;

 n = 8;
 int* array = new int[n];
 for(int i = 0; i < n; ++i)
  array[i] = 0;

 array[0] = n;
 Gen(array, n, 1);

 return 0;
}


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
62.500ms