質問: お世話になります。 プログラミングを学んでいますが、全くわかりません。 心が折れてしまっています。 どなたか、教えてくださいませんか。 問題と実行例等は以下の通りです。何がわからないのか、わからないという状況です。 何卒宜しくお願い致します。 --- **問題** 標準入力から2個の正整数が与えられる。 その2個の正整数の最大公約数を計算して標準出力に書き出すプログラムを作れ。 最大公約数は、左詰にして1行として書き出すこと。 枠組みだけが書き入れてあるので、ここで考えたことを書き加えてプログラムを完成すること。 **実行例** ``` 標準入力 8 15 標準出力 1 ``` ``` #include int main(int argc, char *argv[]){ int a, b; scanf("%d",&a); scanf("%d",&b); // ・・・ a と b の最大公約数を求めて、 // ・・・それを必要最小限の桁数で書き出す。 return 0; } ```
回答: この問題を解くための方法として、以下のステップを順番に確認するやり方が考えられます。 1. 最大公約数とは何かを確認する。 2. 最大公約数を求めるためのアルゴリズムはどのようなものか確認する。 3. そのアルゴリズムを C 言語で実装するためにはどうすれば良いか考える。 4. 入出力の部分をどう実装すれば良いか考える。 今回は「何がわからないのか、わからないという状況」とのことですので、まずはご自身がこの段階のどこで「わからない」になっているのかを確かめることから始めてみましょう。 1. 最大公約数とは何かを確認する。 正の整数 `a` と `b`の最大公約数とは、`a` と `b` の共通の約数のうち、最大のもののことです。 2. 最大公約数を求めるためのアルゴリズムはどのようなものか確認する。 `a` と `b` が与えられたとき、`a` と `b` の最大公約数を求めるためのアルゴリズムはいくつか存在します。 たとえば素朴なものだと、`a` か `b` か小さい方を `i` としたとき、`i` を 1 ずつ減らしながら `a` と `b` が両方割り切れるか確かめていき、最初に割り切れたときの `i` が最大公約数だ、というアルゴリズムがあります。どうしてこれで最大公約数が計算できるかわかりますでしょうか。 他にも、これより効率的に計算ができる有名なアルゴリズムとして、ユークリッドの互除法が知られています。Wikipedia の記事に説明が書かれているので、ご存じなければ読んでみてください。(もし互除法のアルゴリズムによく分からないことがあれば、それを言語化して新しく質問してみてください :) ユークリッドの互除法 -- Wikipedia 3. そのアルゴリズムを C 言語で実装するためにはどうすれば良いか考える。 アルゴリズムはあくまで抽象的な概念なので、それを実際のプログラムとして書く必要があります。 C 言語に備えられたどのような要素を使ってプログラムを書けば良いでしょうか? 繰り返しが必要なら、`for` 文や `while` 文といった繰り返しを表現するための要素が使えます。ユークリッドの互除法を実装するなら「`a` を `b` で割った余り」を計算する必要があり、これは C 言語では `a % b` と書くと計算してくれます。 もし `for` や `while` などがどういうものなのかの時点でわからなくなったら、この問題に取り組む前に何かしら C 言語のチュートリアルをこなすのが良いと思います。授業で指定されているものや、市販されている書籍、あるいはウェブ上の資料が役に立つでしょう。 また、今回のようによく知られた問題の場合は、「最大公約数 プログラム」とか「ユークリッドの互除法」とかでウェブ検索するとソースコードが出てきます。既存のソースコードを読んで、それが何をしているのか確認し、その上で自分で弄って動作を確認したり自分でもう一度書いたりするという方針も取れます。 4. 入出力の部分をどう実装すれば良いか考える。 今回の課題では、`a` と `b` を入力からもらい、そして求まった最大公約数を出力しないといけません。 入力の部分は既に `scanf` として課題のプログラムに書かれているので、後は出力の部分です。これは `printf` を使うのが便利でしょう。