2つの整数a,bを入力すると,aをbで割った時の整数商と余りを出力するプログラム. 除算記号, モジュロ演算子は禁止.
aをbで割った時の整数商と余りを出力するプログラムが分からないのでお願いします.
整数商, 余り
Re: 整数商, 余り
これはプログラムの問題と言うよりは、算数の問題ですね。
これをプログラムでは無く、手作業ですることは出来ると思います。
その手順を詳細に書き出して、それをプログラムにすればできあがりです。
これをプログラムでは無く、手作業ですることは出来ると思います。
その手順を詳細に書き出して、それをプログラムにすればできあがりです。
Re: 整数商, 余り
例えばa = 17, b = 3ならば、整数商 = 5, あまり = 2
となるわけですが、手計算ではどのようにしますか?
となるわけですが、手計算ではどのようにしますか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 整数商, 余り
「コンピュータの内部では、割り算は引き算の繰り返しで実行されています」
と書いてある本を昔読んだことがありますが、そんなことはありません。
実行結果
と書いてある本を昔読んだことがありますが、そんなことはありません。
#include <stdio.h>
int main(void)
{
int a, b, x, y;
x = y = 0;
if (scanf("%d%d", &a, &b) != 2) return 1;
for (int i = 0; i < 32; i++) {
y <<= 1;
if (a < 0) y |= 1;
x <<= 1;
if (y >= b) x |= 1, y -= b;
a <<= 1;
}
printf("%d %d\n", x, y);
return 0;
}
-
- 記事: 48
- 登録日時: 7年前
Re: 整数商, 余り
割り算ルーチンは現代のCPUでは命令として使えますが、この割り算ルーチン
を作るメリットは、割り算の仕組みをアルゴリズムで考えさせるという意味のほかには
遅いCPUのクロスアセンブラで割り算命令がサポートされてなく、
割り算ルーチンを自作する事が有効手段のように思えますが、
それが全てでかつ正しいかどうかは分かりません。
では、まず15÷3は手計算じゃなくて暗算で5と分かりますが、
15-3=12-3=9-3=6-3=3-3=0
と割る数である3を何回引けば、3より下になるかを考える事ができます。
この場合15÷3=5です。
余りが無い割り算の例を出してしまったので、↓の割り算はどうでしょうか。
15÷4=15-4=11-4=7-4=3
となります。割る数の4を何回引けば4より下になるか?を考える事ができます。
この場合、3余り3が答えです。
このように紙にでもPCのメモ帳にでも計算式をコメントで書く事が出来れば
よりよく分かるアルゴリズムです。
を作るメリットは、割り算の仕組みをアルゴリズムで考えさせるという意味のほかには
遅いCPUのクロスアセンブラで割り算命令がサポートされてなく、
割り算ルーチンを自作する事が有効手段のように思えますが、
それが全てでかつ正しいかどうかは分かりません。
では、まず15÷3は手計算じゃなくて暗算で5と分かりますが、
15-3=12-3=9-3=6-3=3-3=0
と割る数である3を何回引けば、3より下になるかを考える事ができます。
この場合15÷3=5です。
余りが無い割り算の例を出してしまったので、↓の割り算はどうでしょうか。
15÷4=15-4=11-4=7-4=3
となります。割る数の4を何回引けば4より下になるか?を考える事ができます。
この場合、3余り3が答えです。
このように紙にでもPCのメモ帳にでも計算式をコメントで書く事が出来れば
よりよく分かるアルゴリズムです。
Re: 整数商, 余り
a = 12345、b = 67 のとき、商は 184 で余りは 17 です。
皆さんは、算数で、手計算で、12345 から 67 を 184回引き算しますか?
誰でも次のように計算しますよね。 67の倍数を右にずらすよりも、
12345を左にずらすほうがコードが簡単になります。
コンピュータの内部では 10進ではなく 2進ですが、
アルゴリズムは同じです。いや、倍数は不要で、
引ければ 1、引けなければ 0 なので、より簡単です。
ただ、y と a の 2つの変数をシフトするのは少し面倒です。
でも、a の最上位ビットを見て、それを yの最下位ビットに
挿入すればよいだけです。
#4 のプログラムはそうなっています。
皆さんは、算数で、手計算で、12345 から 67 を 184回引き算しますか?
誰でも次のように計算しますよね。 67の倍数を右にずらすよりも、
12345を左にずらすほうがコードが簡単になります。
y a b x
00000 12345
00001 23450 <<
00001 23450 - 67 x 0
00012 34500 <<
00012 34500 - 67 x 0
00123 45000 <<
00056 45000 - 67 x 1
00564 50000 <<
00028 50000 - 67 x 8
00285 00000 <<
00017 00000 - 67 x 4
アルゴリズムは同じです。いや、倍数は不要で、
引ければ 1、引けなければ 0 なので、より簡単です。
ただ、y と a の 2つの変数をシフトするのは少し面倒です。
でも、a の最上位ビットを見て、それを yの最下位ビットに
挿入すればよいだけです。
#4 のプログラムはそうなっています。
Re: 整数商, 余り
筆算で割り算をするときに、「何回引き算が出来るか」で行うことは通常はありません。
しかし、割り算を禁止と言われれば一番最初に思いついたのがそれです。同時に余りも求まりますし。
例えば、50÷8 を計算するときほぼ暗算で 6 あまり 2 と出ますが、50から8を引いてもたいした手間ではありません。もちろん桁数が大きくなると大変ですが、小さい桁で出来れば桁が大きくなってても、手順は同じです。
「割り算は引き算の繰り返しで出来る」と授業で教わったかどうかはすでに記憶があやふやで、
定かではないのですが、一般常識として理解していました。
ビットシフトで割り算が出来るのは、プログラミングを勉強し始めてから知りましたが、
自分で思いつくのはなかなか難しいと思いました。
被除数と除数の差が大きいと効率が悪くなるのはすぐに気がつくつと思いますが、
それを改善すると課題に対する評価が高くなるかもしれませんね。
しかし、割り算を禁止と言われれば一番最初に思いついたのがそれです。同時に余りも求まりますし。
例えば、50÷8 を計算するときほぼ暗算で 6 あまり 2 と出ますが、50から8を引いてもたいした手間ではありません。もちろん桁数が大きくなると大変ですが、小さい桁で出来れば桁が大きくなってても、手順は同じです。
「割り算は引き算の繰り返しで出来る」と授業で教わったかどうかはすでに記憶があやふやで、
定かではないのですが、一般常識として理解していました。
ビットシフトで割り算が出来るのは、プログラミングを勉強し始めてから知りましたが、
自分で思いつくのはなかなか難しいと思いました。
被除数と除数の差が大きいと効率が悪くなるのはすぐに気がつくつと思いますが、
それを改善すると課題に対する評価が高くなるかもしれませんね。