#UVa:441-Lotto

灆洢 2015-05-08 02:37:41

利用遞迴(backtracking)把所有可能性列舉出來並輸出即可。

C++(0.009)

/*******************************************************/
/* UVa 441 Lotto                                       */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2015/05/08                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

const int LOTTO_SIZE = 6;

void printPermutation(int lotto[], int n, int k, int permutation[], int p){
  if( p >= LOTTO_SIZE ){
    for( int i = 0 ; i < LOTTO_SIZE ; ++i ){
      if( i > 0 ) printf(" ");
      printf("%d", permutation[i]);
    }
    printf("\n");
    return;
  }

  if( p + (k - n) < LOTTO_SIZE ) return ;

  for( int i = n ; i < k ; ++i ){
    permutation[p] = lotto[i];
    printPermutation(lotto, i+1, k, permutation, p+1);
  }
}

int main(){
  bool hasPrinted = false;
  int k;
  while( scanf("%d", &k) != EOF && k != 0 ){
    if( hasPrinted ) printf("\n");

    int lotto[15];
    for( int i = 0 ; i < k ; ++i ){
      scanf("%d", &lotto[i]);
    }

    int permutation[LOTTO_SIZE] = {0};
    printPermutation(lotto, 0, k, permutation, 0);
    hasPrinted = true;
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料