アルゴリズムを考えながらプログラミングを書く練習のために、以下の問題を解いてみます。
問題.1
100円玉が8枚、1000円札が8枚、1万円札が2枚あるとき
指定された金額に1番おつり額が少なく、使用枚数の少ない組み合わせを答えなさい
問題.2
問題１ようなパターンで、いろんな種類、いろんな枚数で組み合わせを出せるプログラムを、なるべくソースコードの修正が少ない形で実現しなさい
お金を支払う際に所持金の状況に合わせて、支払う貨幣の組み合わせパターンを考えるというものです。
皆さんがお買い物の際に普段やっていことを、プログラムでさせようというわけです。
例えば金額が3200円だとしたら「1000円札が3枚、100円玉が2枚」が答えになりますね。
6480円だとしたら「1000円札が6枚、100円玉が5枚」になります。
3900円だとしたら「1000円札が4枚」になります。
9100円だとしたら「10000円札が1枚」になります。
このように指定された金額を満たすように、貨幣の組み合わせを答えるのが今回のプログラムとなります。
問題.2については、所持金の異なるパターンの計算を、なるべくソースの修正範囲の少ない形で実装してくださいというものです。
つまり500円玉が増えた場合でも、ソースを極力修正することなく対応できるようにしようということですね。
ここでの修正というのは、アルゴリズムを変えなくてすむという意味です。
問題1のパターンでしか対応できないというのは、汎用性がないアルゴリズムとなります。
まずは所持貨幣を管理するための構造体定義です。
どの貨幣を何枚持っているかが分かればいいので要素は2つになりますが、何枚使うかも覚えなきゃいけないのでついでに使用枚数も構造体の中に含めてしまいます。
// 貨幣情報
typedef struct
{
int money; // 金額
int quantity; // 所持数
int useNum; // 使用数
}MoneyInfo;構造体が定義出来たら、問題に合わせて実態を作成します。
int main()
{
MoneyInfo moneyInfo[] = {
{ 100, 8, 0},
{ 1000, 8, 0},
{10000, 2, 0},
};
}設定は小さい貨幣から順番に並んでいるものとします。
次に指定金額の入力を行います。
int destValue;
while (true)
{
printf("目標金額=");
scanf_s("%d", &destValue);
if (destValue == 0) break;
Calc(destValue, moneyInfo, sizeof(moneyInfo) / sizeof(MoneyInfo));
}
scanfで金額を入力します。
0が指定されたらプログラムを終了します。
Calcという関数の中で計算を行います。
目標金額と貨幣情報を引数に渡します。
結果はCalc関数の中で表示して終わるので、戻り値は特にありません。
それではCalcの中身を作っていきます。
その前にアルゴリズムを考えます。
アルゴリズムは、基本的には「自分だったらどうやって解くか？」を考えるところから始まります。
分かりやすくシンプルが良いです。
さて自分が支払いの際に「どのように貨幣を組み合わせて支払うか」を考えればよいことになります。
まず値の大きい貨幣から使っていきます。
例えば14800という金額が指定されたとします。
まず1万円札を1枚持っていれば必ず1枚は使います。
（たとえ1000円札を10枚持っていたとしても、1万円札を使ったほうが使用枚数は少なくなりますよね）
次にその貨幣よりも値の小さい貨幣を合算して、残りの金額を支払えるかどうかをチェックします。
もし全部合わせても支払えなければ、1万円札をもう一枚使います。
つまり1万円札以下の貨幣で4800円が支払えれば1万円札の使用枚数は1枚となり、支払えなければ1万円札の使用枚数は2枚となります。
小さい貨幣で支払える場合は、今度は千円札で考えます。
残りの4800円を千円札を何枚使用するかを考えます。
4枚ある場合は4枚使用します。
次にその貨幣よりも値の小さい貨幣を合算して、残りの金額を支払えるかどうかをチェックします。
もし全部合わせても支払えなければ、千円札をもう一枚使います。
今回は100円玉で残りの800円が支払えるので、千円札の使用は4枚となります。
これら一連の流れが頭の中でイメージできない場合は、実際にお金を使って試してみるといいでしょう。
プログラムにするために、これら一連のフローをチャートに落とし込みます。
- 一番高い貨幣からスタートする。
必要な残り金額を指定された金額に設定する。 - 現在の貨幣で必要最低限の枚数を計算する。
必要な残り金額から枚数分の金額を引く。
必要な残り金額が0になったら終了する。 - 現在の貨幣より下の貨幣の合計金額を出し、必要な残り金額と比較して足りるかどうかチェックする。
足りない場合は、今の貨幣を1枚足して終了する。
（1枚足せない場合はそもそも払えない） - 現在の貨幣を1つ下の貨幣に設定して２に戻る。
大体こんな感じになるかと思います。
細かい部分やロジックのミスなどは、組みながら考えたり組んだ後のデバッグで見つけるとします。
これをプログラムに落とし込んでいきます。
// 計算処理
void Calc(int money, MoneyInfo* info, int infoNum)
{
// 使用数の初期化
for (int i = 0; i < infoNum; i++)
{
info[i].useNum = 0;
}
// 必要な残り金額
int needValue = money;
for (int i = (infoNum - 1); i >= 0; i--)
{
int useNum = (needValue / info[i].money);
useNum = (info[i].quantity < useNum) ? info[i].quantity : useNum;
info[i].useNum = useNum;
needValue -= info[i].money * useNum;
if (needValue <= 0)
{
break;
}
// 現在の貨幣より下の貨幣の合算を計算する
int totalValue = 0;
for (int j = (i - 1); j >= 0; j--)
{
totalValue += info[j].money * info[j].quantity;
}
if (totalValue < needValue)
{
// 下の貨幣じゃ足りないので今の貨幣をもう一枚使用する
if (info[i].useNum == info[i].quantity)
{
// 足りないので支払えない
printf("払えません。\n\n");
return;
}
info[i].useNum++;
needValue -= info[i].money;
break;
}
}
// 結果表示
for (int i = 0; i < infoNum; i++)
{
printf("%d円=%d枚\n", info[i].money, info[i].useNum);
}
printf("おつり%d円\n\n", -needValue);
}以上となります。
ここで１つ問題が出ます。
MoneyInfo moneyInfo[] = {
{ 100, 3, 0},
{ 2000, 3, 0},
{ 5000, 2, 0},
{10000, 2, 0},
};このような場合に、9500円などを指定すると、5000円札1枚と2000円札3枚で支払おうとしてしまいます。
10000円札で払ったほうが、おつりも使用する枚数は減りますよね。
つまり結果に対して、大きい貨幣に両替できる場合は両替する必要があります。
結果を表示する前に以下の両替処理を入れます。
// 上の貨幣で両替できる場合は行う（なるべく大きい貨幣を使う）
for (int i = (infoNum - 1); i >= 1; i--)
{
if (info[i].quantity == info[i].useNum)
{
continue;
}
// 今の貨幣より下の貨幣の使用合計金額を計算する
int useMoney = 0;
for (int j = (i - 1); j >= 0; j--)
{
useMoney += info[j].useNum * info[j].money;
}
if (useMoney < info[i].money)
{
// 両替出来ない
continue;
}
// 両替出来る可能性がある
MoneyInfo* tmpInfo = new MoneyInfo[infoNum];
int tmpNeedValue = needValue;
bool abort = false;
memcpy(tmpInfo, info, sizeof(MoneyInfo) * infoNum);
useMoney = tmpInfo[i].money;
for (int j = (i - 1); j >= 0; j--)
{
int val = tmpInfo[j].useNum * tmpInfo[j].money;
useMoney -= val;
tmpNeedValue += val;
tmpInfo[j].useNum = 0;
if (useMoney < 0)
{
if (useMoney < needValue)
{
abort = true;
}
break;
}
else if (useMoney == 0)
{
break;
}
}
if (!abort)
{
tmpInfo[i].useNum++;
needValue = tmpNeedValue - tmpInfo[i].money;
memcpy(info, tmpInfo, sizeof(MoneyInfo) * infoNum);
}
}組み合わせ計算よりも両替処理の方が長くて複雑になってしまいましたね…
いくつかパターンを試してみて、問題無さそうであればひとまず完成です。
もし結果がおかしくなるパターンを見つけたら、こっそり教えてくださいね。
さて、上のプログラムでは貨幣の組み合わせによって結果がおかしくなる可能性を持っています。
ロジックエラーと呼ばれるものです。
プログラムのバグではなく、そもそも考え方がおかしいというものです。
別のアルゴリズムでロジックエラーの少ない方法を考えてみましょう。
シンプルなのは、組み合わせの全パターンを出して、その中からおつり額と使用枚数の少ない組み合わせを選ぶという方法です。
これなら確実ですね。
ただし所持金の貨幣パターンを全てチェックするので、枚数が多いと計算処理が爆発的に増えます。
アルゴリズムはたくさんあります。
皆さんも「こういうふうにやったらもっと簡単にできるんじゃないか？」ってアイデアがあったら、是非試してみてください。
コメント