promotion image of download ymail app
Promoted
YOyo 發問時間: 電腦與網際網路程式設計 · 7 年前

幫我解離散數學程式

3.1: 寫一個程式, 利用產生所有的排列來解決TSP問題

Input: the first line is an integer n, n<=10. In the next n lines, there is an n*n matrix

Output: the minimum cost of the Hamiltonian cycle

3.2: 寫一個程式, 輸入n and r, generate all combinations of choosing r out of n.

1 個解答

評分
  • sponge
    Lv 6
    7 年前
    最佳解答

    以下兩段 code 請參考:

    // 3.1.cpp

    #include <algorithm>

    #include <climits>

    #include <cstdio>

    using namespace std;

    int main(){

    int n, a[10][10], min_cost=INT_MAX, i, j;

    scanf("%d", &n);

    int v[10]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d", &a[i][j]);

    do{

    j=0;

    for(i=0; i<n; i++) j+=a[i][(i+1)%n];

    if(j<min_cost) min_cost=j;

    }while(next_permutation(v, v+n));

    printf("The minimal cost is %d.\n", min_cost);

    return 0;

    }

    // 3.2.cpp

    #include <algorithm>

    #include <cstdio>

    using namespace std;

    int main(){

    int n, r, i, *a;

    scanf("%d%d", &n, &r);

    a=new int[n];

    for(i=0; i<n-r; i++) a[i]=0;

    for(i=n-r; i<n; i++) a[i]=1;

    do{

    for(i=0; i<n; i++) printf("%d", a[i]);

    putchar('\n');

    }while(next_permutation(a, a+n));

    delete[] a;

    return 0;

    }

    其中用到 next_permutation 請見參考資料

    它功用是將陣列內元素排列,共有 n! 個可能性

    3.1 題目未說明 n*n 矩陣各元素的意義

    因此回答終將它看作邊的 cost

    3.2 也未說明被挑選的每個元素如何表達

    因此只印出 0/1, 用 1 表示被選到者

    3.2 寫法將 n 取 r 的問題看成 n-r 與 r 個相同物的排列

    希望如上對您有幫助!

    • Commenter avatar登入以對解答發表意見
還有問題?馬上發問,尋求解答。