配列を再帰的に縮小して新しいパラメータとして渡す

Question

配列の要素を削除し続ける（つまり、1番目、2番目などを扱うときに配列を縮小する）ことが可能ですか？新しいパラメータとして渡します同じ関数（つまり再帰的）に？

お客様の変更に必要な各コインの数を計算する簡単な方法を考えていますが（自動販売機など）、ネストループを使用するすべてのGoogle検索結果で混乱しています...（私が理解しにくいことを意味する）私は、私がこの問題を解決するための簡単な再帰呼び出しに私の思考を翻訳できるかどうかを見極めることにしました。

私がこれまで持っていたことは次のとおりです。例えば、10,20,50,100、そして200コインの金種リストがあれば、マシンは80セントを返すとします。人間は考えるだろう：最初の硬貨は80よりも小さいので50セントであるので、50セントにする必要があり、残りは30セントになります。

30未満の最初のコインは20セントですので、残りの残りのコインは10セントです。残りの部分よりも少ない（またはこの場合は等しい）最初のコインは、10セントで処理を完了します。

それで、各ステップで、私を助ける最大の硬貨の貨幣を世話した後、私はあまりにも多くの他の大きな硬貨を「無視する」。すなわち、私は役に立たないコインの金種を取り除いています。

私は単純な思考方法をコード化していますが、私は次のことを思いつきましたが、今この "コインデノミネーション配列縮小"をコードにどのようにマッピングできるのでしょうか？これは私がtemp配列を置いたところでハイライトされています...

私が始めたとき、私はcoins[1]であった2ユーロの硬貨（200）をチェックしました。だからcoins[2]は1ユーロだった。そして、50セントのコインがソートされました（coins[3]）ので、今度はcoins[4]とcoins[5]に同じメソッドCalculateを実行したいと思います。これはインデックス4と5だけを含む新しい軸配列と考えることができます問題を解決し続けることができます。

これも可能ですか？

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 


namespace CoinsConsole 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            int[] coins = new int[5] { 200, 100, 50, 20, 10 }; 

            Calculate(coins, 80); // 50 + 20 + 10 

            Console.ReadLine(); 
        } 


        static []int Calculate(int[] coins, int change) 
        { 
            int[] counts = new int[5] { 0, 0, 0, 0, 0 }; 
            int remaining; 

            for (int i = 1; i <= coins.Length; i++) 
            { 
                if (coins[i] <= change) 
                { 
                    remaining = change - coins[i]; 
                    ++counts[i]; 
        []int temp = coins.Skip(i); 
                    Calculate(temp, remaining); 
                } 
            } 

            return counts; 
        } 
    } 
} 

編集1：これは単なるarray.Skip(n).Take(n)の複製ではありません。再帰のために変更された配列を渡す方法を理解しようとしています。例えば私はarray.Copyまたは同じ打ち切ら配列を、使用する必要があるかどうかなど...

EDIT 2：私は私が新しい短縮配列に渡すべきだと思う方法を取り入れているが、coins.Skip(i)とCalculate(temp, remaining)は、すべての赤下線を付しています。私は間違って何をしていますか？

Answer 1

私はあなたの問題への回答を投稿していますが、他の回答は、あまりにも複雑すぎて、あなたが間違った考えをすることはできません。

static void CalculateChange(int change, int[] coins) 
{ 
    Console.Write(change + " = "); 

    int j = 0; 
    while (change > 0) 
    { 
     for (int i = j; i < coins.Length; i++) 
     { 
      int coin = coins[i]; 
      if (coin <= change) 
      { 
       change = change - coin; 
       j = i; // remmeber the position of the biggest possible coin, to start from next loop 
       Console.Write(coin + " "); 
       break; 
      } 
     } 
    } 
} 

ご覧のとおり、かなり近いです。

ここで、変数jは、内側forループを最適化することです。最後に使用したコインの位置を思い通りにして、もう一度大きなコインをチェックする必要はありません。

プログラムはまだjで動作します。私は残りのコインを減らすというあなたの考えに合うようにそこに置きました。

2つの注意点：まず、この回答はint[] coinsが降順にソートされていることを前提としています。第二に、これはiteraitveのアプローチです、私はあなたが再帰的なものを解決すると確信しています。

Answer 2

この方法は通常、再帰呼び出しごとにサブアレイを抽出することにより、ではなく、です。代わりに、開始インデックスと考慮する要素の数とともに、常に正確に同じ配列を渡すことによって行われます。

このようにして、サブアレイを抽出するという面倒な作業をする必要がなくなり、コードのパフォーマンスが大幅に向上します。

メソッドのパブリックインターフェイスを変更したくない場合は、すべてのジョブ（再帰を含む）を実行する内部（プライベート）メソッドを呼び出して開始インデックスおよび配列に0を渡します。長さの長さ。

サブアレイの抽出を主張する場合は、サブアレイを自分で割り当ててからArray.Copyを使用して、古いアレイから新しいアレイに要素の範囲をコピーする必要があります。 https://msdn.microsoft.com/en-us/library/system.array.copy(v=vs.110).aspx

Answer 3

これはあなたの質問に答えることはできませんが、他の可能な、より簡単なアプローチに目を向けるかもしれません。

コインスタックの分別容器はありますか？以下の構造を考えてみよう：Dictionary<int, Stack<Coin>>。このコンテナには、値（セント）で分類されたコインのスタックがあります。

coins[10]は、マシンで利用可能なすべての10セントのコインのスタックを提供します。 coins[25]はあなたに四半期などを与えます

お客様がコインを追加する場合は、適切なスタックに入れてください：coins[enteredCoin.Value].Push(enteredCoin)。

これにより、異なる通貨で自動販売機を簡単に設定することもできます。スタートアップでは、辞書に登録してコイン（キー）を受け取り、自動販売機をプリチャージします（スタックを積み重ねてコインを押す）。

入力されたコインが受け入れ可能かどうかを確認することも簡単です。値が辞書の有効なキーであるかどうかをチェックします。そうでない場合は、顧客に返します。

この手法では、作業がはるかに簡単になります。