4

順序が重要でない場合の組み合わせであるnCrのすべての可能性を印刷しようとしています。したがって、5C1には5つの可能性があります：1、2、3、4、5。5C2には10の可能性があります：1 2、1 3、1 4、1 5、2 3、2 4、2 5、3 4、3 5 45。

r = 2、r = 3、r = 4の場合に必要なものを出力する関数を作成し、パターンを確認しましたが、変数rの有効なメソッドを作成できないようです。

public void printCombinationsChoose2(int n, int k) //for when k = 2
{
    for (int a = 1; a < n; a++)
    {
        for (int b = a + 1; b <= n; b++)
        {
            System.out.println("" + a + " " + b);
        }
    }
}

public void printCombinationsChoose3(int n, int k) //for when k = 3
{
    for (int a = 1; a < n - 1; a++)
    {
        for (int b = a + 1; b < n; b++)
        {
            for (int c = b + 1; c <= n; c++)
            {
                System.out.println("" + a + " " + b + " " + c);
            }
        }
    }
}

public void printCombinationsChoose4(int n, int k) //for when k = 4
{
    for (int a = 1; a < n - 2; a++)
    {
        for (int b = a + 1; b < n - 1; b++)
        {
            for (int c = b + 1; c < n; c++)
            {
                for (int d = c + 1; d <= n; d++)
                {
                    System.out.println("" + a + " " + b + " " + c + " " + d);
                }
            }
        }
    }
}

public void printCombinations(int n, int k) //Doesn't work
{
    int[] nums = new int[k];
    for (int i = 1; i <= nums.length; i++)
        nums[i - 1] = i;

    int count = 1;

    while (count <= k)
    {
        for (int a = nums[k - count]; a <= n; a++)
        {
            nums[k - count] = a;

            for (int i = 0; i < nums.length; i++)
                System.out.print("" + nums[i] + " ");
            System.out.println();
        }
        count++;
    }
}

ですから、私の最後のメソッドのレイアウトは正しいと思いますが、私が呼び出すとprintCominbations(5, 2)、それが印刷されるので、私は正しいことをしていません。

1 2 
1 3 
1 4 
1 5 
1 5 
2 5 
3 5 
4 5 
5 5

5C2について前に言ったはずのとき。

編集 最後の例は悪かった。これは、それが間違っていることを説明するためのより良いものです：printCombinations(5, 3)これを与えます：

1 2 3 
1 2 4 
1 2 5 
1 2 5 
1 3 5 
1 4 5 
1 5 5 
1 5 5 
2 5 5 
3 5 5 
4 5 5 
5 5 5

どうすれば次のようになりますか。

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
4

5 に答える 5

7

これはどう：

public class Test {

    public static void main(final String[] args) {
        print_nCr(7, 4);
    }

    public static final void print_nCr(final int n, final int r) {
        int[] res = new int[r];
        for (int i = 0; i < res.length; i++) {
            res[i] = i + 1;
        }
        boolean done = false;
        while (!done) {
            System.out.println(Arrays.toString(res));
            done = getNext(res, n, r);
        }
    }

    /////////

    public static final boolean getNext(final int[] num, final int n, final int r) {
        int target = r - 1;
        num[target]++;
        if (num[target] > ((n - (r - target)) + 1)) {
            // Carry the One
            while (num[target] > ((n - (r - target)))) {
                target--;
                if (target < 0) {
                    break;
                }
            }
            if (target < 0) {
                return true;
            }
            num[target]++;
            for (int i = target + 1; i < num.length; i++) {
                num[i] = num[i - 1] + 1;
            }
        }
        return false;
    }
}

私にとってこの解決策の鍵は、問題を記数法として見ることでした。あなたは数を1つずつ増やしたいので、上限に達するたびに、余剰分を左に運ぶだけです。増加するアルゴリズムを正しく実装する必要があります。

于 2011-10-03T06:56:51.853 に答える
4

コードが期待から外れる最初のポイントは次のとおりです。

...
1 2 5 
1 2 5    <-- first bad output
1 3 5
...

したがって、3つのことを自問してください。

  • 変数の特定の状態で、そのコード行で何が起こったはずですか？

  • なぜ私のコードは正確にそれをしないのですか？

  • それを達成するために何を変更する必要がありますか？

最初の部分の答えは次のようになります。

  • 2toをインクリメントし、の初期化と同様3に、次の数値を、、...に設定する必要が 4あり5ます。nums

2番目と3番目の部分は再びあなたの部分です。

ところで：さらに助けが必要なために戻ってきたときは、これまでに推測したことを詳しく説明し、質問を整理してかなり短くしてください。

于 2011-10-02T18:09:39.063 に答える
1

OK ...ループが必要であるが、ループの数は必要ないことがわかっている場合の解決策は何ですか？RECURSION...再帰的な実装を使用する必要があります。これを覚えておいてください：いつでもループが必要ですが、ネストされたループの数は、問題の特定のパラメーターに基づいて、実行時にのみ知ることができます。再帰的な方法を使用する必要があります...試してみる時間を与えますそれはあなた自身です、私はあなたに最終的な実装を与えるために戻ってきます...

于 2011-10-02T15:06:24.143 に答える
1

私はC++でそれをしました

#include <iostream>

using namespace std;
#define ARR_LIMIT 100
int arr[ARR_LIMIT];

void _ncr(int N,int R, int n,int r , int start )
{
    if(r>0)
    {
        for(int i = start ; i <= start + (n-r); i++)
        {
            arr[R-r] = i;
            _ncr(N,R,N-i, r-1, i+1 );
        }
    }
    else
    {
        for(int i=0;i<R;i++)
        {
            cout << arr[i] << " ";
            if(i==R-1)
                cout<<"\n";
        }
    }

}

void ncr(int n,int r)
{
    //Error checking of parameters
    bool error = false;
    if( n < 1)
    {
        error = true;
        cout<< "ERROR : n should be greater 0 \n";
    }
    if( r < 1)
    {
        error = true;
        cout<< "ERROR : r should be greater 0 \n";
    }
    if(r > n)
    {
        error = true;
        cout<< "ERROR : n should be greater than or equal to r \n";
    }
    // end of Error checking of parameters
    if(error)
        return;
    else
        _ncr(n,r,n,r,1);
}

int main()
{
    int n,r;
    cout << "Enter n : ";
    cin >> n;
    cout << "Enter r : ";
    cin >> r;
    ncr(n,r);
    return 0;
}
于 2013-02-27T11:01:24.103 に答える
0

関数のレイアウトがprintCombination()間違っているようです。whileループは、forcount = 1と。の2回繰り返されcount = 2ます。

の場合count = 1、この場合はの値のみnums[0][here]が変更されk - count = 1ます。したがって、
1,21,31,4 および
1,5 。

そして、の場合count = 2、ここから、の値のみnums[here][1]が変更されますk - count = 0。したがって 、
1,5
2,53,54,5 および
5,5

于 2011-10-02T14:26:04.530 に答える