d115

輸入說明 ：

本題有多組測試資料。

每組測試資料有一行，第一個數n，接下來有n個數 A1~An，這些數不會有重覆的 ，最後有一個數 m。

若n=0請結束程式，不必輸出任何資料。

輸出說明 ：

你可以輸出:

1."我一點都不喜歡妳!!" (不含雙引號) 她就會因為過度傷心而讓你得到WA。

2.由小到大，依序列出從這n個數中選出m個號碼的所有可能 (請參考範例測資)。她就會因為過度開心而讓你得到AC。 全部可能輸出後請空一行。

這題是用遞迴的窮舉,我一開始不會寫ˇ,都是先看演算法筆記,然後改它的程式碼,

這題是有n個東西,要你找出任取m個的問題,把所有可能性.印出來,就是C n取m的所有可能

for(i=0+index;i<n;i++)
    {
            s[c]=a[i];
            ++index;
            re(c+1,index);
    }

這是最重要的部分 假設現在有1,2,3,4,5,6 六個數字在a[]裡面,我要任取三個

我現在先把1放進s[0], 進入遞迴檢查是不是已經拿三個了(已經拿幾個由變數c來控制),還沒現在才拿第一個,接著我把2放進s[1],進入遞迴檢查是不是已經拿三個了,還沒我現在才拿兩個,接著我把3放進s[2],進入遞迴檢查,我已經拿三個了,

再來我要回到s[1]放2那步的for迴圈的下一步,然後做完s[1]放3,s[1]放4,s[1]放5,s[1]放6

在回到s[0]放1那步的for回圈,把s[0],變成放2.......

index是拿來控制,我取到的數字不會是前面的,不然會重複

#include<stdio.h>
#include<algorithm>
int n,m;
int a[120];
int s[120];

void re(int c,int index)
{    
    int i;
    if(c==m)
    {
        for(i=0;i<m;i++)
            printf("%d ",s[i]);
        puts("");
        return;
    } 

    for(i=0+index;i<n;i++)
    {
            s[c]=a[i];
            ++index;
            re(c+1,index);
    }

}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);

        scanf("%d",&m);
        std::sort(a,a+n);

        re(0,0);
    }
}