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

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

新規登録して質問してみよう
ただいま回答率
85.51%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

3回答

1265閲覧

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

langhtorn

総合スコア104

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2020/05/20 14:58

編集2020/05/21 03:33

###実現したいこと
三つ以上の整数の最大公約数を求める。
###問題点

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

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

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

###コード

C++

1#include<iostream> 2#include<cstdlib> 3int main(int argc,char* argv[]) 4{ 5 int maxk=0; 6 int ans=0; 7 int i,j,k; 8 for(i=1;i<argc;i++){ 9 for(j=std::atoi(argv[i]);j>0;j--){ 10 if(std::atoi(argv[i])%j==0){ 11 if(std::atoi(argv[i+1])%j==0){ 12 ans=j; 13 break; 14 } 15 } 16 for(k=ans;k>0;k--){ 17 if(ans%k==0){ 18 if(std::atoi(argv[i+2])%k==0){ 19 maxk=k; 20 break; 21 } 22 } 23 } 24 } 25 } 26 std::cout<<"最大公約数は"<<maxk<<"\n"; 27 return 0; 28}

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Yasumichi

2020/05/20 15:50 編集

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

2020/05/20 15:51

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

2020/05/20 16:17

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

2020/05/20 16:39

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

回答3

0

ベストアンサー

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

./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 で割って余りがあるかどうかを見ればよいのです。

C++

1#include <iostream> 2#include <cstdlib> 3 4int main(int argc, char* argv[]) 5{ 6 int maxk = 0; 7 int i, j; 8 for (i = std::atoi(argv[1]); i > 0; i--) { 9 for (j = 1; j < argc; j++) { 10 if (std::atoi(argv[j]) % i != 0) break; 11 } 12 if (j == argc) { 13 maxk = i; 14 break; 15 } 16 } 17 std::cout << "最大公約数は " << maxk << "\n"; 18 return 0; 19}

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

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

投稿2020/05/20 19:08

kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

langhtorn

2020/05/21 09:37

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

0

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

c++

1#include<iostream> 2#include<cstdlib> 3using namespace std; 4 5int main(int argc,char* argv[]) 6{ 7 int maxk=0; // 最大公約数 8 int i; 9 int j; 10 11 // プログラムを除き2つ以上の引数が与えられなかった場合 12 if (argc < 3) { 13 cout << "2つ以上の整数を入力してください。" << endl; 14 return -1; 15 } 16 17 // 以下、例外処理は省略 18 19 // 引数の最小値を求めつつ、配列に格納 20 int size = argc - 1; // コマンド以外の引数の数 21 int *num = new int[size]; 22 num[0] = atoi(argv[1]); 23 int min = num[0]; 24 for(i=1;i<size; i++) { 25 num[i] = atoi(argv[i+1]); 26 if (min > num[i]) { 27 min = num[i]; 28 } 29 } 30 31 // 共通な数で割れるだけ割っていく 32 for(i=min; i>0; i--) { 33 bool flg = true; // すべて割り切れるか否か 34 for(j=0; j<size; j++) { 35 if (num[j] % i != 0) { 36 // 割り切れなかったので false にしてループを抜ける 37 flg = false; 38 break; 39 } 40 } 41 // この時点で flg が true ならばすべて割り切れたということ 42 if (flg == true) { 43 maxk = i; 44 break; 45 } 46 } 47 48 // 結果の表示 49 cout<<"最大公約数は"<<maxk<<"\n"; 50 return 0; 51}

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

投稿2020/05/20 17:16

Yasumichi

総合スコア1773

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

参考情報

  • 【競プロ】3個以上の整数の最大公約数と最小公倍数

https://math.nakaken88.com/textbook/cp-gcd-and-lcm-of-many-integers/

投稿2020/05/20 23:25

katoy

総合スコア22322

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.51%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問