用递归算法实现一个小程序（菜鸟我确实没分了）(50分)

有一道题是说：找出n个自然数（1,2,...,n）中r个数的组合。例如n=5,r=3所有组合为：
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
对于这道题树上说可以用递归来实现，说是5个数中取3个可以推到4个数中去2个...
但是所给的程序不能运行（结果乱七八糟），我也想不通如何实现，特来想高手请教！

地去找本 c 语言方面的书 一般的都有这个源程序

用循环也可以实现啊：（如下程序可以参考，未必正确）
for i:= 5do
wnto 3do
for j:= i-1do
wnto 2do
for k:= j-1do
wnto 1do
write(i,j,k)

搞定了：） 分可要全给我哦：）

function GetList(value: integer;s: string): string;
//看清楚哦，这个不是类方法，不要搞错了：）
var
i, j: integer;
begin
if Length(s) <> (value - 2) then
begin
for i := 1 to valuedo
begin
if (pos(inttostr(i),s) = 0 ) then
GetList(value,s+inttostr(i));
end
end
else
begin
Form1.Memo1.Lines.Add(s);
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
Memo1.Lines.Clear;
GetList(strtoint(Edit1.Text),'');
Label1.Caption := inttostr(Memo1.Lines.Count);
end;

呵呵，
运行出来了，不过运行的结果是所有可能的排列情况，能不能改成组合情况

我研究了一下你的算法，实际上还是一个穷举法的原理，包装成了递归，反正是完成了任务
不过好像不好改成组合方式。

可以用的，搞定了：） 分可要全给yxyyyy哦：）

function GetList(value: integer;s: string): string;
var
i, j: integer;
begin
if Length(s) <> 3 then
begin
for i := 1 to valuedo
begin
if ((s='')or((pos(inttostr(i),s)=0)and(strtoint(s[length(s)])>i))) then
GetList(value-1,s+inttostr(i));
end
end
else
begin
Form1.Memo1.Lines.Add(s);
end;
end;

当然，解决这个问题，用递归是费力不讨好，但有递归确实很有意思。
看了各位仁兄的贴子，收获颇多。（稍侯，我再琢磨各位的思路）
我先说说我对这个问题的看法，请各位指正。
将各种情况罗列出来以后，发现它确实是可以用数学的递归算法来解决。
我们设函数f(n,r)，可以得到一个从1..n的数列中选r个数，而得到的一组数。
这里，我们用向量的形式表示某一组数，然后得到的就是向量的集合。
就是说f(n,r)得到一组r维向量的集合。
如f(5,3)={(5,4,3);(5,4,2);(5,4,1);(5,4,3);(5,3,2);(5,3,1);(5,2,1);(4,3,2);(4,3,1);(3,2,1);}
那么有：
递归公式：f(n,r)=n ※ f(n-1,r-1) + f(n-1,r)
其中※运算为左侧元素填加至右侧r-1向量中，而形成r向量 的运算符
递归终止条件：f(n,0)={} f(n,1)={(1)(2)..} f(n,n)={(1,2..n)}
正好最近看C++看的头痛，那就用C++写了，因为C++中正好有vector（向量）对象，
不知道Object Pascal该怎么写？
/*
* 从1..n序列中选r个数，用递归实现
* 递归公式 f(n,r)=n ※ f(n-1,r-1) + f(n-1,r)
* 其中 ※ 为左侧元素填加至右侧r-1维向量中，而形成r维向量
* 终止条件 f(n,0)={} f(n,1)={(1),(2)..} f(n,n)={(1,2,..n)}
*
*/


#include <iostream.h>
#include <conio.h>
#include <vector>
#include <system.hpp>
#include <dstring.h>

// ※ 运算符
vector <AnsiString> ad(int n, const vector<AnsiString> &amp;
vecN)
{
vector <AnsiString> vecAd;
AnsiString strN;
vecAd=vecN;
for (int i=0 ;i<vecAd.size();++i)
{
strN=vecAd;
strN=strN+IntToStr((unsigned));
vecAd=strN;
}
return vecAd;
}
//两个向量的+ 运算
vector <AnsiString> plusN(const vector<AnsiString> &amp;
lha,const vector<AnsiString> &amp;
rha)
{
vector <AnsiString> vecPN;
AnsiString elem;
vecPN=lha;
for (int i=0;
i<rha.size();++i)
{
elem=rha;
vecPN.push_back(elem);
}
return vecPN;
}

//求f(n,r)
vector <AnsiString> select_num(int n,int r)
{
vector <AnsiString> vecSNum;
AnsiString elem="";
if (r==0 || n==0)
{
vecSNum.clear();
return vecSNum;
}
if (r==1)
{
vecSNum.clear();
for (int i=1;i<=n;++i)
{
elem=IntToStr((unsigned int)(i));
vecSNum.push_back(elem);
}
return vecSNum;
}
if (n==r)
{
vecSNum.clear();
elem="";
for (int i=1;i<=n;i++)
{
elem=elem+IntToStr((unsigned)(i));
}
vecSNum.push_back(elem);
return vecSNum;
}
//递归
vecSNum=plusN(ad(n,select_num(n-1,r-1)),select_num(n-1,r));
return vecSNum;
}
int main()
{
vector <AnsiString> SN;
SN=select_num(30,1);
for (int i=0;
i<SN.size();++i)
{
cout<<SN<<endl;
}
getch();
return 0;
}
//---------------------------------------------------------------------------

c++无所谓,运行结果正确（好像顺序有点乱，不过没关系）
先谢过了，然我好好消化一下！ ：—）

回溯算法就可以
你再消化一下吧!

chinaplate的分析过程给了我很大的启发
我终于写出了真正的递归函数
program Project2;
{$APPTYPE CONSOLE}
uses SysUtils;
var
S: String;
procedure Comba(n,r: Integer;
S: String);
var
nI: Integer;
begin
if r=0 then
exit;
// 空集
if r=1 then
// 回归
for nI:=ndo
wnto 1do
writeln(s,' ',nI)
else
// 递推
for nI:=ndo
wnto n-r+1do
Comba(nI-1,r-1,s+' '+IntToStr(nI));
end;

begin
comba(5,3,S);
end.

我发现要写一个递归函数的关键就是要找出它的递推条件和回归条件，把这两个条件理顺了
写起来就很方便了。
递推：(n,r) (r<>0,r<>1)
(n-1,r-1) (n-2,r-1) ... (n-r+1,r-1)
回归：(n,r)
(r=0) 返回空集
(r=1) 显示 n,n-1,...1
谢谢大家，
发分了！！！！！！

对不起，程序有误，更正如下
program Project2;
{$APPTYPE CONSOLE}
uses SysUtils;
var
S: String;
procedure Comba(n,r: Integer;
S: String);
var
nI: Integer;
begin
if r=0 then
exit;
// 空集
if r=1 then
// 回归
for nI:=ndo
wnto 1do
writeln(s,' ',nI)
else
// 递推
for nI:=ndo
wnto rdo
Comba(nI-1,r-1,s+' '+IntToStr(nI));
end;

begin
comba(5,3,S);
end.

我发现要写一个递归函数的关键就是要找出它的递推条件和回归条件，把这两个条件理顺了
写起来就很方便了。
递推：(n,r) (r<>0,r<>1)
(n-1,r-1) (n-2,r-1) ... (r,r-1)
回归：(n,r)
(r=0) 返回空集
(r=1) 显示 n,n-1,...1

看了一下你的程序，思路更清晰了，比我的简练多了，效率也高，我做的是个花架子，不能
干活的，你要是用它做彩票机f(30,7)，能把计算机给累死。
递归这个东西，蛮好玩的，思路清晰了，程序就很好写了。
下面是我的一个同事，从一本书上找来的程序（好象是什么程序员之类的），和你的思路
不谋而合。
#include <iostream.h>
#include <conio>
const int MAXN=100;
int n,r;
int a[100];

sel(int m,int k)
{
int i,j;
for (i=m;i>=k;i--)
{
a[k-1]=i;
if (k>1) sel(i-1,k-1);
else
{
for(j=r-1;j>=0;j--)
cout<<a[j];
cout<<endl;
}
}
}
void main()
{
n=5;
r=3;
sel(n,r);
getch();
}

彩票机????!!!!!
我刚用程序算了一下,31选7共有2629575种组合，几率太小了

多人接受答案了。