質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.61%

ユークリッド互除法を使わずに最大公約数を求めたい

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,342

score 94

実現したいこと

三つ以上の整数の最大公約数を求める。

問題点

最大公約数が違う答えになる。
./kadai09 40 45 50
"最大公約数は0"

追記5/21

私なりにいただいた助言をもとに考えなおしてみました。でもうまくいかないです。

やりたいこととしては、まずargc[1]とargc[2]の最大公約数を求めて、その答えとargc[3]の最大公約数を求めるというのをどんどん繰り返していく、、、というかんじです。

コード

#include<iostream>
#include<cstdlib>
int main(int argc,char* argv[])
{
    int maxk=0;
    int ans=0;
    int i,j,k;
    for(i=1;i<argc;i++){
        for(j=std::atoi(argv[i]);j>0;j--){
        if(std::atoi(argv[i])%j==0){
            if(std::atoi(argv[i+1])%j==0){
                ans=j;
                break;
            }
        }
        for(k=ans;k>0;k--){
            if(ans%k==0){
                if(std::atoi(argv[i+2])%k==0){
                    maxk=k;
                    break;
                }
            }
        }
    }
    }
    std::cout<<"最大公約数は"<<maxk<<"\n";
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Yasumichi

    2020/05/21 00:48 編集

    argv[0] には、実行ファイル名が入るのは理解していますか?また、argc には、実行ファイル名も含めた引数の数が入ります。

    キャンセル

  • Yasumichi

    2020/05/21 00:51

    入力例も提示してください。最初の引数に数の個数を入れる想定でしょうか?

    キャンセル

  • Yasumichi

    2020/05/21 01:17

    スルーされてるかもしれませんが。
    一度、計算のイメージを数式だけで書いてみた方が良さそうです。今のループだと存在しない argv[i] を読み込んでいます。

    キャンセル

  • Yasumichi

    2020/05/21 01:39

    共通な数で割れるだけ割っていく方法をやりたいということですね。

    キャンセル

回答 3

checkベストアンサー

+3

まず自分の書いたコードがどういう動きをするのか確かめてください。

./kadai09 40 45 50 で起動したということは、

  • argc = 4
  • argv[0] = "./kadai09"
  • argv[1] = "40"
  • argv[2] = "45"
  • argv[3] = "50"
  • argv[4] = NULL

となっています。

for文の i = std::atoi(argv[1]) で、i は 40 になります。
i > 0 だから、中に入ります。
if文の std::atoi(argv[i]) ですが、argv[40] なんか参照してはいけません。

for文で、i が 40 から 1 まで変化します。これが最大公約数の候補です。
argv[1]、argv[2]、argv[3] の全部を割り切れるものを見つけるわけだから、argv[j]
として j を 1 から 3 まで変えて i で割って余りがあるかどうかを見ればよいのです。

#include <iostream>
#include <cstdlib>

int main(int argc, char* argv[])
{
    int maxk = 0;
    int i, j;
    for (i = std::atoi(argv[1]); i > 0; i--) {
        for (j = 1; j < argc; j++) {
            if (std::atoi(argv[j]) % i != 0) break;
        }
        if (j == argc) {
            maxk = i;
            break;
        }
    }
    std::cout << "最大公約数は " << maxk << "\n";
    return 0;
}


非常に効率の悪いコードですが、とりあえず正しく動くはずです。

この回答についてのコメントをお願いします。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/05/21 18:37

    iが盲点でした。アドバイスありがとうございました。

    キャンセル

+1

あまり美しくないし、例外処理もしていませんが、以下のようなコードでいかがでしょうか?

#include<iostream>
#include<cstdlib>
using namespace std;

int main(int argc,char* argv[])
{
    int maxk=0; // 最大公約数
    int i;
    int j;

    // プログラムを除き2つ以上の引数が与えられなかった場合
    if (argc < 3) {
        cout << "2つ以上の整数を入力してください。" << endl;
        return    -1;
    }

    // 以下、例外処理は省略

    // 引数の最小値を求めつつ、配列に格納
    int size = argc - 1;    // コマンド以外の引数の数
    int *num = new int[size];
    num[0] = atoi(argv[1]);
    int min = num[0];
    for(i=1;i<size; i++) {
        num[i] = atoi(argv[i+1]);
        if (min > num[i]) {
            min = num[i];
        }
    }

    // 共通な数で割れるだけ割っていく
    for(i=min; i>0; i--) {
        bool flg = true;    // すべて割り切れるか否か
        for(j=0; j<size; j++) {
            if (num[j] % i != 0) {
                // 割り切れなかったので false にしてループを抜ける
                flg = false;
                break;
            }
        }
        // この時点で flg が true ならばすべて割り切れたということ
        if (flg == true) {
            maxk = i;
            break;
        }
    }

    // 結果の表示
    cout<<"最大公約数は"<<maxk<<"\n";
    return 0;
}

ちょっと問題とずらしてますし、using namespace std; とか使っているのであれですが。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

参考情報

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る