学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。

#include <stdio.h>

/* 正整数 n, m の最大公約数を計算する */
int gcd(int n, int m) {
int res;

res = n % m;

if (res == 0)
return m;/* 最大公約数が求まった */

return gcd(m, res);/* 再帰呼び出し */
}

int main(void) {
int i,j;

for(i=10000;i>=10;i--){
for(j=10;j=10000;j++){
printf("%d to %d no saidaikouyakusuu ha %d \n", i, j, gcd(i, j));
}
}

return (0);
}

です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。

A 回答 (1件)

未検証


>for(j=10;j=10000;j++){
少なくとも真ん中の条件の=は誤り。それ以外に思いつくミスは特にない
    • good
    • 0
この回答へのお礼

回答ありがとうございます。

直したらちゃんと動きました。

お礼日時:2009/05/22 11:39

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qユークリッドの互除法について

13を9で割ると 1.444…の循環小数で表せますが,
このわり算の筆算ができる理由をユークリッドの互除法で説明したいと考えています。

ユークリッドの互除法について いくつかの文献を読みましたが どれも 最大公約数を求める方法として紹介されています。

筆算ができる理由としてユークリッドの互除法をどのように使えばよいか ご回答の程よろしくお願いします。

Aベストアンサー

ユークリッドの互除法では無理です。
互除法はたとえば97を9でわってあまりが7.次に「9を7でわって」、とします。
割り算は97を9でわってあまりが7、7を9では割れないので、10倍して(十進法なので)「70を9で」わります。
このように2回目以降割る順番が違う上、10倍して(10進法の場合。n進法ならn倍)しまうので、同様の計算とはいえません。この程度の類似なら例えば開平の計算なども同様の計算になってしましますが、これは明らかに異質です。
ですから、「筆算ができる理由としてユークリッドの互除法をどのように使えばよいか」に対する答えはどのように使っても無理、といのが答えになります。

Qint select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout)について

見当違いな質問かもしれませんがお願いします。

複数のソケットを監視する際にselectを使う場合のことですが、
selectの動作と戻り値について疑問があります。

http://www.linux.or.jp/JM/html/LDP_man-pages/man2/select.2.html
ここを参照すると、selectの戻り値は
「更新された 3 つのディスクリプタ集合に含まれているディスクリプタの数 (つまり、 readfds, writefds, exceptfds 中の 1 になっているビットの総数) を返す。」
とあります。
私の中でselectは登録してあるFDのうち、一つでも動きがあれば即座にselectを抜けるもの、という認識です。
この認識だとreadfds,writefdsが引数として与えられているとしても、
どちらかのfd_setのうち、一つでも動きがあればselect文は
抜けてしまうことになります。とすると、戻り値として
「readfds, writefds, exceptfds 中の 1 になっているビットの総数」
は常に1ということになってしまいます。しかし、総数というからには
複数同時に1になることもあるはずです。

私の認識が間違っているとは思うのですが、どう間違っているのかわかりません。
select文の動きについて詳しく教えていただけないでしょうか。
または良いページがあれば教えてください。

見当違いな質問かもしれませんがお願いします。

複数のソケットを監視する際にselectを使う場合のことですが、
selectの動作と戻り値について疑問があります。

http://www.linux.or.jp/JM/html/LDP_man-pages/man2/select.2.html
ここを参照すると、selectの戻り値は
「更新された 3 つのディスクリプタ集合に含まれているディスクリプタの数 (つまり、 readfds, writefds, exceptfds 中の 1 になっているビットの総数) を返す。」
とあります。
私の中でselectは登録してあるFDのうち、一つでも動きが...続きを読む

Aベストアンサー

>私の中でselectは登録してあるFDのうち、一つでも動きがあれば即座にselectを抜けるもの、という認識です。
この認識はあっています。
しかし、selectを呼び出す以前にOKになっているFDがあれば、それらは全てビットがONになります。

話しを簡単にする為に、受信のみのソケットを3つ作成したとします。
これらの3つのソケットに向けて相手が電文を送ったとします。
その状態でまだ、こちらはselectを呼び出さずにいます。しばらくしてから、selectを呼び出すと、selectは即座にリターンし、3つのビットが一度にONになっているはずです。
一方、相手が、一切電文を送ってない状態で、selectを呼び出した場合は、何れかのビットがONになればリターンするので、そのときは、貴方が想像しているように
ビットの総数は1になる可能性が高いです。
従って、相手が電文を送る前にselectを呼び出すか、送った後にselectを呼び出すかは、その時のタイミングにより異なります。従って、ビット数の総和が常に1であるとは、考えない方が無難です。(1つのソケットしか使用しない場合は別ですが・・・)

>私の中でselectは登録してあるFDのうち、一つでも動きがあれば即座にselectを抜けるもの、という認識です。
この認識はあっています。
しかし、selectを呼び出す以前にOKになっているFDがあれば、それらは全てビットがONになります。

話しを簡単にする為に、受信のみのソケットを3つ作成したとします。
これらの3つのソケットに向けて相手が電文を送ったとします。
その状態でまだ、こちらはselectを呼び出さずにいます。しばらくしてから、selectを呼び出すと、selectは即座にリターンし、3つのビ...続きを読む

Q【数学】ユークリッドの互除法のごじょほうってどういう意味ですか? ユークリッドの互除法を考えたユーク

【数学】ユークリッドの互除法のごじょほうってどういう意味ですか?

ユークリッドの互除法を考えたユークリッドってユークリッド幾何の人と同じ人物ですか?別人ですか?

ユークリッドってどんな人だったのか教えてください。偉伝の伝説が聞きたいです。

あとユークリッド幾何とユークリッドの総除法ってどんなことなのか教えてください。簡単に。

Aベストアンサー

「互除法」は、文字通りの意味です。「互」は、「お互いに」の意味、「除」は、「除算をする」の意味、「法」は、「方法」の意味です。
それをまとめて、「(2つの数について)お互いに割り算をしていく方法」という意味になります。

ユークリッド幾何学のユークリッドと同じ人です。ユークリッドの「(幾何学)原論」」の中に、幾何学も、数論(互除法も書かれている)も書かれている(そうです。私は読んだことがないので、、、)。

ユークリッド幾何学は、われわれが体験する幾何学的な事実を厳密な形で整理したものです。
ユークリッド幾何学だけを説明するより、非ユークリッド幾何学と一緒にして違いを説明した方が分かりやすいと思いますので、3つまとめて説明します。
これらの幾何学は、平行線の公理が成立するかどうかによって特徴付けられます。まず、平行線の公理は、次のように述べられます。

[公理] 1本の直線と、その直線上にない1点に対して、その点を通るその直線に平行な直線がただ1本だけ存在する。

この公理が成立する幾何学が、ユークリッド幾何学です。

この公理が成立しない幾何学が、非ユークリッド幾何学です。公理の否定の形によって、2つの幾何学が考えられます。
公理の前半部分は同じですので、省略して後半だけ書きます。
1つ目は、
  .....、平行な直線は存在しない。
2つ目は、
  ......、平行な直線が2本(以上)存在する。
となります。

ユークリッドの互除法(もともとの記述は、互減法だそうですが)は、2つの自然数 m, n の最大公約数を求める方法です。以下のように表されます。

 a: 2つの数の大きい方を小さいほうで割った余り r を求める。
 b:  r が 0 ならば、割った数が、最大公約数として終了する。
 c: そうでなければ、割った数を大きい方の数とし、余りを小さい    方の数として、a に戻る。
(互減法の場合は、a のところの割り算の代わりに、引けなくなるまで引き算を繰り返す、に変わります。結果として、余りを求めていることになります。)

ユークリッドの伝記は、自分で調べてください。

「互除法」は、文字通りの意味です。「互」は、「お互いに」の意味、「除」は、「除算をする」の意味、「法」は、「方法」の意味です。
それをまとめて、「(2つの数について)お互いに割り算をしていく方法」という意味になります。

ユークリッド幾何学のユークリッドと同じ人です。ユークリッドの「(幾何学)原論」」の中に、幾何学も、数論(互除法も書かれている)も書かれている(そうです。私は読んだことがないので、、、)。

ユークリッド幾何学は、われわれが体験する幾何学的な事実を厳密な形で整理...続きを読む

Qvoid (*signal(int signum, void (*handler)(int)))(int);

の解釈を教えてください
最後の「(int)」については詳しくお願いします

Aベストアンサー

signalが

(1)1つ目の引数の型:int
(2)2つ目の引数の型:引数がintで戻り値がvoidである関数へのポインタ
(3)戻り値の型:引数がintで戻り値がvoidである関数へのポインタ(2と同じ)

を満たす関数である事を宣言しています。最後の(int)はsignalの戻り値の
関数ポインタがint型の引数を持つ事を示しています。

「引数がintで戻り値がvoidである関数へのポインタ」の型をHANDLERと表すと

HANDLER signal(int signum, HANDLER handler);

となります。

Qユークリッドの互除法を使う問題なのですが、 下線部がなぜ次の行のようになるのか分かりません(;;)

ユークリッドの互除法を使う問題なのですが、
下線部がなぜ次の行のようになるのか分かりません(;;)
教えて下さい、よろしくお願いします!(*_ _)

Aベストアンサー

9×1-22×2+9×4
=9×1+9×4-22×2
=9×(1+4)-22×2
=9×5-22×2

Qint i,j; \n i=0,j=5;

int i,j;
i=0;
j=5:
と書いてあるソースは普通ですが、
int i,j;
i=0,j=5:
と書いてあるソースもあります。
後者はC++の正しい書式ですか?

カンマ演算子というのは後者のカンマのことですか?

Aベストアンサー

 正しい書式です。

i=0,j=5;
 における、「,」をカンマ演算子といいます。2項の演算子です。カンマで区切られた演算を「左から順番に」実行し、最後の演算を結果として返します。
 したがって、例の文であれば、i=0を実行し、次にj=5を実行。そして、j=5の結果の5を結果として返します。
 ・・・
 が、本来的には、あまり、例のような使い方はしませんね。よく見られるのは、次のような場合です。

 for (i=0,j=0 ; i < 50 ; ++i,++j) {

 のような形でよく見られます。for文の各式は、一つの式でなければならないので、こんな書き方をするわけです。初期化と更新部が一つにまとまり、ループが読みやすくなるのが利点かな。

Qユークリッドの互除法についての問題です。

ユークリッドの互除法についての問題です。

a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。

(1)aが5の倍数でないとき ax≡b (mod5)
(2)aが4の倍数でないとき ax≡b (mod4)


誰か教えてください。

Aベストアンサー

すべては下の掛け算表でわかります。

(1)

0| 0 1 2 3 4
----------
0| 0 0 0 0 0
1| 0 1 2 3 4
2| 0 2 4 1 3
3| 0 3 1 4 2
4| 0 4 3 2 1

0,1,2,3,4がちゃんとそろっています。

(2)

0| 0 1 2 3
--------
0| 0 0 0 0
1| 0 1 2 3
2| 0 2 0 2
3| 0 3 2 1

0,2だけになるのがあります。

Q「void ( *signal(int sig, void (*func)(int)) ) (int)」の (int)

signal関数の書式についてですが、

  void ( *signal(int sig, void (*func)(int)) ) (int);

最後に付く(int)は一体何でしょうか?
このような関数の書式ははじめて見ました。
UNIX系の何かでしょうか。
回答よろしくお願いします。

Aベストアンサー

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t sighandler);
より後半部分のtypedefを置き換えると
sighandler_t signal(int signum, void (*sighandler)(int));
つぎに戻り値の部分のtypedefを置き換えると
void (*signal(int signum, void (*sighandler)(int)))(int);
となります。
(
sighandler_t signal(int signum, void (*sighandler)(int));
の「signal(int signum, void (*sighandler)(int))」をAと置き換えて
sighandler_t A;
からtypedefを置き換えると
void (*A)(int);
となり、Aを戻すと
void (*signal(int signum, void (*sighandler)(int)))(int);
となる。
)

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t sighandler);
より後半部分のtypedefを置き換えると
sighandler_t signal(int signum, void (*sighandler)(int));
つぎに戻り値の部分のtypedefを置き換えると
void (*signal(int signum, void (*sighandler)(int)))(int);
となります。
(
sighandler_t signal(int signum, void (*sighandler)(int));
の「signal(int signum, void (*sighandler)(int))」をAと置き換えて
sighandler_t A;
からtypedefを置き換...続きを読む

Qユークリッドの互除法

ユークリッドの互除法の証明の一部なのですが
aをで割った商をbあまりをrとすると
a=bq+r であるので r=a-bq である。ここで、この右辺はa bの最大公約数でわり切れるのは、なぜか教えて下さい。あと a bの最大公約数がrとb
の公約数でもあるのはなぜですか?お願いします。

Aベストアンサー

a,bの最大公約数をkとすると、
r=a-bq
r=ka'-kb'q
r=k(a'-b'q)

なので、割り切れる。

Q{x = x>y ? x:y; return x;}

#include <iostream>
using namespace std;

inline int max(int x, int y){x = x>y ? x:y; return x;}

int main()
{
int num1, num2, ans;

cout << "2つの整数を入力して。\n";
cin >> num1 >> num2;

ans = max(num1, num2);

cout << "最大値は" << ans << "です。\n";

return 0;
}
の{x = x>y ? x:y; return x;}の部分の意味が解りません。

Aベストアンサー

inline int max(int x, int y){x = x>y ? x:y; return x;}
これを普通に関数で書くと

int max(int x, int y)
{
x = x>y ? x:y;
return x;
}

です。

x = 部分は右辺の結果が代入されます。これはわかりますよね。
x>y?x:y;
と書くと?より左にある条件式を判定し、その結果が真である場合は:で区切られた左側の値を、偽である場合は右の値を帰します。
x>yが真であればxを、偽であればyを返します。
それが、左辺値xに代入され、関数の戻り値として帰ります。

従って、2つの値をこの関数に入れると、大きいほうの値が帰ることになります。


人気Q&Aランキング