- PR -

お手本になるようなソースコード

投稿者

投稿内容

Anonymous Coward: 会議室デビュー日: 2007/05/09; 投稿数: 8

投稿日時: 2007-05-11 23:44

＞カーニーさん
ああっ、早くも新たなお題が…と思ったら、
Ver2を現実的なシチュエーションに書き換えてくださったのですね。
ありがとうございます。

私も考えてみました。

皆さんとは違うアプローチで、柔軟性より速度重視です。
＃というと聞こえはいいですが、手作業を介入させた泥くさいやり方です。

まず、紙幣を10000,8000,5000,2000,1000に限定して考えれば、
残額が40000未満になるまでは、万券を使うのが最も枚数が少なくなるので、
入力値を40000以上の部分、硬貨部分、残りの３つに分けました。

すると残りの部分は39000以下の1000の倍数となります。

次に、あまり頭の良い方法ではないのかもしれませんが、
手作業で1000～39000まで総当たりで枚数最小パターンを調べてみました。
すると、パターンには以下の４種類あることがわかりました。
(1) 解が１つで、かつそれがVer1と同じロジックにて求められる（例：35000）
(2) 解が１つで、かつそれはVer1と同じロジックでは求められない（例：34000）
(3) 解が複数あり、その全てが1枚以上の万券を含む（例：31000）
(4) 解が複数あり、かつそのいずれかが万券を1枚も含まない（例：37000）

しかし、それぞれのパターンが現れる数字の間に法則性は見出せなかったので、
switchで分岐させてベタ書きすることにしました。
ただし、(3)と万券を含む(2)はあらかじめ万券分を差し引いて分岐の数を減らしてます。
柔軟性は全然ありませんが、ループで候補を探索するプログラムより速度は速いです。

以下がC#のコードです。

コード:

class Program
{
    static int[] PaperUnits = { 10000, 8000, 5000, 2000, 1000 };
    static int[] CoinUnits = { 500, 100, 50, 10, 5, 1 };

    static void Main(string[] args)
    {
        int money;
        if (args.Length <= 0 || !int.TryParse(args[0], out money) || money < 0)
        {
            Console.WriteLine("引数に0以上の整数を指定してください。");
            return;
        }

        //40000以上の部分と下3桁と残りに分ける
        int coins = money % 1000;
        money -= coins;
        int remain = money;
        int yukichi = 0;
        if (money >= 40000)
        {
            remain = money % 10000 + 30000;
            yukichi = (money - remain) / 10000;
        }

        //硬貨を数える
        int[] coinResults = new int[CoinUnits.Length];
        CountCoin(coins, 0, coinResults);

        //紙幣を数える
        List<int[]> paperResultsList = new List<int[]>();
        int[] paperResults = new int[PaperUnits.Length];

        //残りの紙幣は以下の４パターン
        // (1) 解が１つで、かつそれがVer1と同じロジックにて求められる
        //  1～12, 15, 18, 19, 20, 22, 25, 28, 30, 35, 38
        // (2) 解が１つで、かつそれはVer1と同じロジックでは求められない
        //  13, 16, 23, 24, 26, 33, 34, 36
        // (3) 解が複数あり、その全てが1枚以上の万券を含む
        //  27, 31, 39
        // (4) 解が複数あり、かつそのいずれかが万券を1枚も含まない
        //  14, 17, 21, 29, 32, 37

        //メインのswitchの分岐を減らすため、パターン(3)および
        //パターン(2)で万券を含むものは万券分引いておく
        switch (remain / 1000)
        {
            case 27:
            case 31:
            case 39:
            case 23:
            case 26:
            case 34:
                remain -= 10000;
                yukichi += 1;
                break;
            case 33:
            case 36:
                remain -= 20000;
                yukichi += 2;
                break;
        }
        //パターン(1),(2)および(4)の第一候補
        switch (remain / 1000)
        {
            case 13:
                AddPaperResults(8000, 1, paperResults);
                AddPaperResults(5000, 1, paperResults);
                break;
            case 16:
                AddPaperResults(8000, 2, paperResults);
                break;
            case 24:
                AddPaperResults(8000, 3, paperResults);
                break;
            default:
                CountPaper(remain, 0, paperResults);
                break;
        }
        paperResultsList.Add(paperResults);
        //パターン(4)の第二候補以降
        switch (remain / 1000)
        {
            case 14:
                paperResults = new int[PaperUnits.Length];
                AddPaperResults(8000, 1, paperResults);
                AddPaperResults(5000, 1, paperResults);
                AddPaperResults(1000, 1, paperResults);
                paperResultsList.Add(paperResults);
                break;
            case 17:
                paperResults = new int[PaperUnits.Length];
                AddPaperResults(8000, 2, paperResults);
                AddPaperResults(1000, 1, paperResults);
                paperResultsList.Add(paperResults);
                break;
            case 21:
                paperResults = new int[PaperUnits.Length];
                AddPaperResults(8000, 2, paperResults);
                AddPaperResults(5000, 1, paperResults);
                paperResultsList.Add(paperResults);
                break;
            case 29:
                paperResults = new int[PaperUnits.Length];
                AddPaperResults(8000, 3, paperResults);
                AddPaperResults(5000, 1, paperResults);
                paperResultsList.Add(paperResults);
                break;
            case 32:
                paperResults = new int[PaperUnits.Length];
                AddPaperResults(8000, 4, paperResults);
                paperResultsList.Add(paperResults);
                break;
            case 37:
                paperResults = new int[PaperUnits.Length];
                AddPaperResults(10000, 2, paperResults);
                AddPaperResults(8000, 2, paperResults);
                AddPaperResults(1000, 1, paperResults);
                paperResultsList.Add(paperResults);

                paperResults = new int[PaperUnits.Length];
                AddPaperResults(8000, 4, paperResults);
                AddPaperResults(5000, 1, paperResults);
                paperResultsList.Add(paperResults);
                break;
        }

        //結果の表示
        foreach (int[] results in paperResultsList)
        {
            Console.Write("{0}*{1}", PaperUnits[0], results[0] + yukichi);
            for (int i = 1; i < results.Length; i++)
            {
                Console.Write("+{0}*{1}", PaperUnits[i], results[i]);
            }
            for (int i = 0; i < coinResults.Length; i++)
            {
                Console.Write("+{0}*{1}", CoinUnits[i], coinResults[i]);
            }
            Console.WriteLine();
        }
    }

    static void AddPaperResults(int unit, int count, int[] results)
    {
        switch (unit)
        {
            case 10000: results[0] += count; break;
            case 8000: results[1] += count; break;
            case 5000: results[2] += count; break;
            case 2000: results[3] += count; break;
            case 1000: results[4] += count; break;
        }
    }

    static void CountPaper(int money, int index, int[] results)
    {
        if (money <= 0) return;
        int unit = PaperUnits[index];
        int count = money / unit;
        results[index] = count;
        CountPaper(money - (unit * count), index + 1, results);
    }

    static void CountCoin(int money, int index, int[] results)
    {
        if (money <= 0) return;
        int unit = CoinUnits[index];
        int count = money / unit;
        results[index] = count;
        CountCoin(money - (unit * count), index + 1, results);
    }
}

余談ですが、このソースコードは柔軟性もないですし、結果の一部をベタ書きしてるため、
手作業での調査不足やタイプミスによるバグも作り込み易いです。
しかし、少なくとも現状の要件は満たしてますし、
他の方の書かれた柔軟性に富んだソースコードよりも実行速度が速いです。

また、クレジットカードのポイントとなると話は別ですが、
紙幣に関しては現実的にはそんな簡単に新たな金種が追加されることはなく、
そこまで柔軟性を考慮しなくても良いと言えます。

先日の書き込みで、私が
「拡張性、可読性、実行速度、生産性などのバランスを考慮すると奥が深い」
「自分が新人の頃には気づかなかった再発見がある」
と書きましたのは、業務プログラマとしての経験を通して、
必ずしも最もスマートなアルゴリズムだけが求められるものではなく、
TPOや本人の技量によって求められる理想解も変わってくる、という意味も含んでいました。

従って、このスレでは単にスマートなアルゴリズムだけを追求するのではなく、
そういった現実的なTPOも加味して、「この状況／前提ならこれで十分だよね」
ですとか、「このロジックは確かにすごいけど実行速度の面で現実的ではないよね」
みたいな議論も交わして頂けると、情報交換の場としてより有用なのかな、と思います。

ひろれい: ぬし; 会議室デビュー日: 2006/03/02; 投稿数: 486; お住まい・勤務地: 万博開催地

投稿日時: 2007-05-12 09:26

引用:

Anonymous Cowardさんの書き込み (2007-05-11 23:44) より:

余談ですが、このソースコードは柔軟性もないですし、結果の一部をベタ書きしてるため、
手作業での調査不足やタイプミスによるバグも作り込み易いです。
しかし、少なくとも現状の要件は満たしてますし、
他の方の書かれた柔軟性に富んだソースコードよりも実行速度が速いです。

また、クレジットカードのポイントとなると話は別ですが、
紙幣に関しては現実的にはそんな簡単に新たな金種が追加されることはなく、
そこまで柔軟性を考慮しなくても良いと言えます。

先日の書き込みで、私が
「拡張性、可読性、実行速度、生産性などのバランスを考慮すると奥が深い」
「自分が新人の頃には気づかなかった再発見がある」
と書きましたのは、業務プログラマとしての経験を通して、
必ずしも最もスマートなアルゴリズムだけが求められるものではなく、
TPOや本人の技量によって求められる理想解も変わってくる、という意味も含んでいました。

従って、このスレでは単にスマートなアルゴリズムだけを追求するのではなく、
そういった現実的なTPOも加味して、「この状況／前提ならこれで十分だよね」
ですとか、「このロジックは確かにすごいけど実行速度の面で現実的ではないよね」
みたいな議論も交わして頂けると、情報交換の場としてより有用なのかな、と思います。

ちょっと気になったので書かせて下さい。

本スレのテーマは「お手本になるようなソースコード」ですよね？
Anonymous Coward さんは、そのテーマを元にソースを書かれたのでしょうか？

「少なくとも現状の要件は満たしてますし」とか「そこまで柔軟性を考慮しなくても良いと言えます」といった言葉に「逃げ」を感じてしまうのは、僕だけでしょうか・・・

確かに、金種なんてそうそう変わるものではありませんが、2,000円札の廃止なんて結構現実的だと思ってみたり(^_^;)

僕個人の感想としては、Anonymous Coward さんのソースを保守することになった場合、余程仕様書がしっかり書かれているかコメントが丁寧に書いてないと理解するのに時間がかかるかなぁ、と思いました。保守性の面で厳しいのかな、と。

あと、「他の方の書かれた柔軟性に富んだソースコードよりも実行速度が速いです」は実際に試されてのご意見でしょうか？

せっかくのいい流れに水を差すようでごめんなさいm(_ _)m
じゃあ言うなよ！って？ｗ

ひろれい: ぬし; 会議室デビュー日: 2006/03/02; 投稿数: 486; お住まい・勤務地: 万博開催地

投稿日時: 2007-05-12 09:48

引用:
わちゃさんの書き込み (2007-05-11 20:02) より: ひろれいさんのだと、{100,50,49,48,47,1} で、141 円払う場合なんか、ダメみたい。最初の金種は、全通り試しているみたいなんですが、その次の金種を減らした方がいい場合には、もれが出ちゃうみたいです。

すいません。Ver.2 の金種対応しか考えていませんでしたから(^_^;)
じゃあ！ってことで、バージョンアップしてみましたｗ

コード:

        Dim 金種リスト As Integer() = {100, 50, 49, 48, 47, 1}
        '        Dim 金種リスト As Integer() = {10000, 8000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1}
        Dim 最適支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
        Dim 試行金額 As Integer = 0
        Dim 金額 As Integer = Integer.Parse(txtIn.Text)
        Dim 最適枚数 As Integer = Integer.MaxValue

        For n As Integer = 0 To 金種リスト.Length - 1
            For i As Integer = 金額 ￥ 金種リスト(n) To 0 Step -1
                Dim 支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
                Dim 枚数 As Integer = 0

                試行金額 = 金額 - 金種リスト(n) * i
                枚数 += i
                支払方法(n) = i

                ' 割り切れたら、即終了
                If 試行金額 = 0 Then
                    If 枚数 < 最適枚数 Then
                        最適枚数 = 枚数
                        最適支払方法 = 支払方法
                    End If
                    Exit For
                End If

                ' 金種を順にチェックしていく
                For j As Integer = n + 1 To 金種リスト.Length - 1
                    Dim k As Integer = 試行金額 ￥ 金種リスト(j)

                    試行金額 = 試行金額 - 金種リスト(j) * k
                    枚数 += k
                    支払方法(j) = k

                    ' 割り切れたら、終了
                    If 試行金額 = 0 Then
                        Exit For
                    End If
                Next

                If 枚数 < 最適枚数 Then
                    最適枚数 = 枚数
                    最適支払方法 = 支払方法
                End If
            Next
        Next

わちゃさんのおっしゃる通り、ここまで来るとやっぱり総当りチェックしかないんでしょうかねぇ

びしばし: 大ベテラン; 会議室デビュー日: 2002/03/13; 投稿数: 181

投稿日時: 2007-05-12 11:11

引用:
わちゃさんの書き込み (2007-05-11 20:02) より: びしばしさんの、広さ優先探索だと、悩ましい事に１０００万円とかの支払いで、すごい時間がかかりそう。 # 実行してないので、分かりませんが。

そうかもしれません。

ならAnonymous Cowardさんも言われている方法で、探索範囲を狭めてしまえば良さそうです。

・最初に最大金額のもの(10000円)と2番目のもの(8000円)との最小公倍数(40000円)を確保できるだけ確保してしまって、残額(40000円未満)についてのみ探索を行う。

と改変すれば大丈夫でしょう、たぶん。

わちゃ: 大ベテラン; 会議室デビュー日: 2005/12/05; 投稿数: 162; お住まい・勤務地: 東京

投稿日時: 2007-05-12 11:38

複雑な問題は、ほんと、どこかにパターンをみつけて、最適化をしないと
ダメかもしれないですよね。

私も、自分のプログラムは、あまりに遅いので、最適化を試みています。
１０倍ぐらい早くなったのですが、前回５２万回の再帰呼び出しが、３万ぐらいには
減ったのですが、それでも速いとは言い難いです。

そういう意味では、Anonymous Coward さんのようなアプローチが、実際に使う
場合にはいいのかもしれません。

むしろ、わりきって、40000 で割った余りの、千の位と、一万の位の４０パターンで、
結果のテーブルをハードコーディングするぐらいに割り切ってもいいのかも。

ひろれいさんの、コードは、241円を支払い場合に、
100円 + 47円 * 3 が最適解ですが、うまくいかないみたいです。

びしばしさんのも、Ver.2( 8000円つき ) では、よいかと思いますが、
Ver.3( 任意貨幣 )では、うまく動かないかと思います。
# {100, 50, 49, 48, 47, 1} で、141 円や、241 円をやるとわかるかと思います。

unibon: ぬし; 会議室デビュー日: 2002/08/22; 投稿数: 1532; お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)

投稿日時: 2007-05-12 13:41

「お題 Ver.2」対応版です(要求仕様はあくまでも総枚数を減らすことに特化しています)。
前回投稿したのを改良しました。概要はつぎのとおりです。

・金種の種類数の分だけ多段ループをするのは前回と同様ですが、多段ループをシンプルに表現するために再帰を使うようにしました。ネストレベルは金種の種類数までです。
・多段ループで無駄に内側のループをやらないようにするために、早めに打ち切れるケースを見つけて打ち切るようにしました。1円玉を5枚以上使う必要はない、とか、8000円札は5枚以上使う必要はない、という上限値を、事前に最小公倍数を使って厳密に求めています。

常識的な金種ならば、20億円でも高速に動きましたので、実使用では問題ないと思います。金種が大きな素数だと速度面ではダメですが、計算結果はどんな金種でも正確だと思っています。
もっとも、ケアレスミス的なバグは残っているかもしれません。

コード:

import java.util.ArrayList;
import java.util.List;

public class Test {

	/**
	 * 札・硬貨の種類 降順であること
	 */
	private static int[] prices = { 10000, 8000, 5000, 1000, 500, 100, 50, 10, 5, 1 };

	/**
	 * 枚数はこれ未満で足りる。
	 */
	private static int[] maxAmounts = new int[prices.length];

	/**
	 * 小銭をかき集めて出来る金額。
	 */
	private static int[] maxCands = new int[prices.length];

	/**
	 * 支払う金額
	 */
	private static int target = 1999999999;

	/**
	 * ある時点で分かっている最小枚数
	 */
	private static int minMai = Integer.MAX_VALUE;

	/**
	 * 最小枚数の結果(複数あることもあるのでリストになっている)
	 */
	private static List<int[]> results = new ArrayList<int[]>();

	/**
	 * 最大公約数 10000 と 8000 ならば 2000
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcd(int a, int b) {
		if (a < b) {
			return gcd(b, a);
		}

		int m = a % b;
		if (m == 0) {
			return b;
		} else {
			return gcd(b, m);
		}
	}

	/**
	 * 最小公倍数 10000 と 8000 ならば 40000
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int lcm(int a, int b) {
		return (int) ((long) (a * b) / (long) gcd(a, b));
	}

	/**
	 * 枚数を算出する。
	 * 
	 * @param amounts
	 * @return
	 */
	private static int calcMai(int[] amounts) {
		int mai = 0;
		for (int i = 0; i < amounts.length; i++) {
			mai += amounts[i];
		}
		return mai;
	}

	/**
	 * level 以下(等しいものは含む)を計算する。
	 * 
	 * @param level
	 * @param amounts
	 * @return
	 */
	private static int calcCand(int level, int[] amounts) {
		int cand = 0;
		for (int i = 0; i <= level; i++) {
			cand += prices[i] * amounts[i];
		}
		return cand;
	}

	/**
	 * level 以上(等しいものは含む)をクリアする。
	 * 
	 * @param level
	 * @param amounts
	 */
	private static void clearAmounts(int level, int[] amounts) {
		for (int i = level; i < amounts.length; i++) {
			amounts[i] = 0;
		}
	}

	/**
	 * level 以下(等しいものは含む)を出力する。
	 * 
	 * @param level
	 * @param amounts
	 */
	private static void output(int level, int[] amounts) {
		String s = "";
		for (int i = 0; i <= level; i++) {
			if (i > 0) {
				s += " + ";
			}
			s += prices[i] + "*" + amounts[i];
		}
		System.out.println(s);
	}

	/**
	 * 中間結果を保存する。 なお、既知の最小枚数より大きければ保存する必要はない。
	 * 
	 * @param amounts
	 */
	private static void preserve(int[] amounts) {
		int mai = calcMai(amounts);
		if (minMai >= mai) {
			if (minMai > mai) {
				minMai = mai;
				results.clear();
			}
			results.add((int[]) (amounts.clone()));
		}
	}

	/**
	 * 金種ごとの最大必要枚数を求める。
	 */
	private static void initMaxAmounts() {
		/* 要素の値が n の場合、a 枚 (a < n) まで使用すれば良い。 */
		for (int i = 1; i < prices.length; i++) {
			int minLcm = Integer.MAX_VALUE;
			for (int j = 0; j < i; j++) {
				int candLcm = lcm(prices[j], prices[i]);
				if (minLcm > candLcm) {
					minLcm = candLcm;
				}
			}
			maxAmounts[i] = minLcm / prices[i];
		}

		/* 最大の金種は枚数に制限がない。 */
		maxAmounts[0] = Integer.MAX_VALUE;
	}

	/**
	 * この level 以下(等しいものは含む)のすべての金種を、最大必要枚数かき集めて作れる総額を求める。
	 * 
	 * @param level
	 * @return
	 */
	private static void initMaxCands() {
		int maxCand = 0;
		for (int i = prices.length - 1; i > 0; i--) {
			maxCand += prices[i] * (maxAmounts[i] - 1);
			/* 累計した値を格納する。 */
			maxCands[i] = maxCand;
		}
		/* 最大の金種は総額に制限がない。 */
		maxCands[0] = Integer.MAX_VALUE;
	}

	/**
	 * 再帰メソッド
	 * 
	 * @param level
	 *            ループのネストレベル(0 = もっとも外側(10000円), prices.length - 1 = もっとも内側(1円)
	 * @param amounts
	 */
	private static void loop(int level, int[] amounts) {
		for (int i = 0; i < maxAmounts[level]; i++) {
			amounts[level] = i;
			int cand = calcCand(level, amounts);
			if (cand >= target) {
				if (cand == target) {
					preserve(amounts);
				}
				break;
			}
			/* これよりさらに内側のループに入ることができるかを調べる。 */
			if (level + 1 < prices.length) {
				/* これより小さい金種まで計算しても無駄ではないかを調べる。 */
				int diff = target - cand;
				if (diff <= maxCands[level + 1]) {
					/* ゴミをクリアする。 */
					clearAmounts(level + 1, amounts);
					/* 再帰呼び出しする。 */
					loop(level + 1, amounts);
				}
			}
		}
	}

	/**
	 * メイン
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		/* 金種がちゃんと降順になっているかをチェックする。 */
		for (int i = 1; i < prices.length; i++) {
			if (prices[i - 1] <= prices[i]) {
				throw new IllegalStateException();
			}
		}

		/* 金種ごとの最大必要枚数をあらかじめ求める。 */
		initMaxAmounts();

		/* 金種ごとに最大必要枚数を使って作れる金額をあらかじめ求める。 */
		initMaxCands();

		/* 最大必要枚数を表示する。 */
		for (int i = 0; i < prices.length; i++) {
			System.out.println("" + prices[i] + "円 (最大 (" + maxAmounts[i] + " - 1) 枚必要)");
		}

		/* 支払う総額を表示する。 */
		System.out.println("target = " + target);

		/* ループ変数(金種ごとの枚数) */
		int[] amounts = new int[prices.length];

		/* 必要ないが明示的にクリアする。 */
		clearAmounts(0, amounts);
		/* 再帰メソッドへ突入する。 */
		loop(0, amounts);

		/* 結果を表示する。 */
		for (int[] result : results) {
			output(result.length - 1, result);
		}

		/* 終わりのあいさつをする。 */
		System.out.println("計算終了。");
	}
}

これを動かした出力結果も載せておきます。

コード:

10000円 (最大 (2147483647 - 1) 枚必要)
8000円 (最大 (5 - 1) 枚必要)
5000円 (最大 (2 - 1) 枚必要)
1000円 (最大 (5 - 1) 枚必要)
500円 (最大 (2 - 1) 枚必要)
100円 (最大 (5 - 1) 枚必要)
50円 (最大 (2 - 1) 枚必要)
10円 (最大 (5 - 1) 枚必要)
5円 (最大 (2 - 1) 枚必要)
1円 (最大 (5 - 1) 枚必要)
target = 1999999999
10000*199997 + 8000*3 + 5000*1 + 1000*0 + 500*1 + 100*4 + 50*1 + 10*4 + 5*1 + 1*4
10000*199999 + 8000*1 + 5000*0 + 1000*1 + 500*1 + 100*4 + 50*1 + 10*4 + 5*1 + 1*4
計算終了。

--
unibon {B73D0144-CD2A-11DA-8E06-0050DA15BC86}

ひろれい: ぬし; 会議室デビュー日: 2006/03/02; 投稿数: 486; お住まい・勤務地: 万博開催地

投稿日時: 2007-05-12 15:07

＃仕事しなさい！＞俺ｗ

引用:

わちゃさんの書き込み (2007-05-12 11:38) より:

複雑な問題は、ほんと、どこかにパターンをみつけて、最適化をしないと
ダメかもしれないですよね。

私も、自分のプログラムは、あまりに遅いので、最適化を試みています。
１０倍ぐらい早くなったのですが、前回５２万回の再帰呼び出しが、３万ぐらいには
減ったのですが、それでも速いとは言い難いです。

そういう意味では、Anonymous Coward さんのようなアプローチが、実際に使う
場合にはいいのかもしれません。

むしろ、わりきって、40000 で割った余りの、千の位と、一万の位の４０パターンで、
結果のテーブルをハードコーディングするぐらいに割り切ってもいいのかも。

ひろれいさんの、コードは、241円を支払い場合に、
100円 + 47円 * 3 が最適解ですが、うまくいかないみたいです。

Ver.3 のバグ対応が完了しました。が、正直自信ありません。ごめんなさい m(_ _)m
ここ（Ver.3）まで来ると、みなさんが仰っているように何かしらの条件をソース上に加える必要性を感じてしまいます。

僕の改良版でも 7桁（9,999,999）まではそこそこの回答速度ですが、8桁（99,999,999）になると返ってきません（だから、試さないで下さいｗ）。
単純ループだと、もう限界だと思います。実用性からは、ほど遠いですね・・・orz

ダメダメじゃん＞俺

Anonymous Coward さん、ごめんなさい。
Anonymous Coward の考え方の方が正しいのかもしれません。

コード:

        Dim 金種リスト As Integer() = {100, 50, 49, 48, 47, 1}
        'Dim 金種リスト As Integer() = {10000, 8000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1}
        Dim 最適支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
        Dim 試行金額 As Integer = 0
        Dim 金額 As Integer = Integer.Parse(txtIn.Text)
        Dim 最適枚数 As Integer = Integer.MaxValue

        For n As Integer = 0 To 金種リスト.Length - 1
            For i As Integer = 金額 ￥ 金種リスト(n) To 0 Step -1
                Dim 支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
                Dim 枚数 As Integer = 0

                試行金額 = 金額 - 金種リスト(n) * i
                枚数 += i
                支払方法(n) = i

                ' 割り切れたら、即終了
                If 試行金額 = 0 Then
                    If 枚数 < 最適枚数 Then
                        最適枚数 = 枚数
                        最適支払方法 = 支払方法
                    End If
                    Exit For
                End If

                ' 金種を順にチェックしていく
                For m As Integer = n + 1 To 金種リスト.Length - 1
                    Dim 試行金額２ As Integer = 試行金額
                    Dim 支払方法２ As Integer() = New Integer(金種リスト.Length - 1) {}
                    Dim 枚数２ As Integer = 枚数

                    支払方法２ = 支払方法.Clone

                    For j As Integer = m To 金種リスト.Length - 1
                        Dim k As Integer = 試行金額２ ￥ 金種リスト(j)

                        試行金額２ = 試行金額２ - 金種リスト(j) * k
                        枚数２ += k
                        支払方法２(j) = k

                        ' 割り切れたら、終了
                        If 試行金額２ = 0 Then
                            If 枚数２ < 最適枚数 Then
                                最適枚数 = 枚数２
                                最適支払方法 = 支払方法２
                            End If
                            Exit For
                        End If
                    Next
                Next
            Next
        Next

わちゃ: 大ベテラン; 会議室デビュー日: 2005/12/05; 投稿数: 162; お住まい・勤務地: 東京

投稿日時: 2007-05-12 16:27

unibon さんの、最小公倍数、最大公約数を使うのは、
自分もアイデアとしては、あっても、具体的にアルゴリズムにできそうな
気がしなかったので、すげ～と思いました。

ただ、49円硬貨を付け足したときに、次のような結果になってしまいました。

コード:
target = 1999999999 10000199997 + 80003 + 50001 + 10000 + 5001 + 1004 + 500 + 492 + 100 + 50 + 1*1

なぜか、５０円玉を使わずに、４９円と、１円を使っちゃったようです。

ひろれいさん、お仕事お疲れ様です。
私は、普通に休みです。

ひろれいさんの、新しいのは、まだ見てませんが、個人的には単純なループでは、
難しいと思っているので、もうちょっと見てみたいと思っています。

自分のも、再帰が多かったのですが、キャッシュの考え方を使ったら、
予想外に早くなりました。

変なパターンがないか、もうちょっと検証したいのですが、
そろそろ、でかけますので、また後日にでも、、、

«前のページへ 1|2|3|4|5|6|7|8|9|10|11 次のページへ»

＠IT SpecialPR

お手本になるようなソースコード

スキルアップ／キャリアアップ（JOB@IT）