整数商, 余り

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Yuma

整数商, 余り

#1

投稿記事 by Yuma » 5年前

2つの整数a,bを入力すると,aをbで割った時の整数商と余りを出力するプログラム. 除算記号, モジュロ演算子は禁止.
aをbで割った時の整数商と余りを出力するプログラムが分からないのでお願いします.

コード:

#include  <stdio.h>
int main(void)
{
        int a, b, x, y;
        scanf("%d, %d",&a, &b);
        x =  
        y = 
}

Bull
記事: 149
登録日時: 9年前

Re: 整数商, 余り

#2

投稿記事 by Bull » 5年前

これはプログラムの問題と言うよりは、算数の問題ですね。

これをプログラムでは無く、手作業ですることは出来ると思います。
その手順を詳細に書き出して、それをプログラムにすればできあがりです。

box
記事: 2002
登録日時: 13年前

Re: 整数商, 余り

#3

投稿記事 by box » 5年前

例えばa = 17, b = 3ならば、整数商 = 5, あまり = 2
となるわけですが、手計算ではどのようにしますか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

かずま

Re: 整数商, 余り

#4

投稿記事 by かずま » 5年前

「コンピュータの内部では、割り算は引き算の繰り返しで実行されています」
と書いてある本を昔読んだことがありますが、そんなことはありません。

コード:

#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;
}
実行結果

コード:

2100000007 2
1050000003 1

かずま

Re: 整数商, 余り

#5

投稿記事 by かずま » 5年前

#4 のプログラムでも引き算が繰り返されていますが、
昔の本にあった引き算とは、次の意味でした。

コード:

	for (x = 0, y = a; y >= b; y -= b) x++;

littlestream
記事: 48
登録日時: 7年前

Re: 整数商, 余り

#6

投稿記事 by littlestream » 5年前

割り算ルーチンは現代の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のメモ帳にでも計算式をコメントで書く事が出来れば
よりよく分かるアルゴリズムです。

かずま

Re: 整数商, 余り

#7

投稿記事 by かずま » 5年前

a = 12345、b = 67 のとき、商は 184 で余りは 17 です。
皆さんは、算数で、手計算で、12345 から 67 を 184回引き算しますか?
誰でも次のように計算しますよね。

コード:

        184
     ------
   67)12345
       67
       ---
       564
       536
       ----
        285
        268
        ---
         17
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
コンピュータの内部では 10進ではなく 2進ですが、
アルゴリズムは同じです。いや、倍数は不要で、
引ければ 1、引けなければ 0 なので、より簡単です。
ただ、y と a の 2つの変数をシフトするのは少し面倒です。
でも、a の最上位ビットを見て、それを yの最下位ビットに
挿入すればよいだけです。
#4 のプログラムはそうなっています。

Bull
記事: 149
登録日時: 9年前

Re: 整数商, 余り

#8

投稿記事 by Bull » 5年前

筆算で割り算をするときに、「何回引き算が出来るか」で行うことは通常はありません。
しかし、割り算を禁止と言われれば一番最初に思いついたのがそれです。同時に余りも求まりますし。
例えば、50÷8 を計算するときほぼ暗算で 6 あまり 2 と出ますが、50から8を引いてもたいした手間ではありません。もちろん桁数が大きくなると大変ですが、小さい桁で出来れば桁が大きくなってても、手順は同じです。
「割り算は引き算の繰り返しで出来る」と授業で教わったかどうかはすでに記憶があやふやで、
定かではないのですが、一般常識として理解していました。
ビットシフトで割り算が出来るのは、プログラミングを勉強し始めてから知りましたが、
自分で思いつくのはなかなか難しいと思いました。
被除数と除数の差が大きいと効率が悪くなるのはすぐに気がつくつと思いますが、
それを改善すると課題に対する評価が高くなるかもしれませんね。

返信

“C言語何でも質問掲示板” へ戻る