応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

2.プログラミング > 2.3 アルゴリズム

■H25春
問7 配列Aに対して次の手続を実行して,2≦k≦100である素数kだけを全て出力したい。a,b,cに入るループの初期値,終値,増分として,適切な組合せはどれか。

for k = 2 to 100 step 1:
  A[k] = 1;
for m = 2 to 10 step 1:
    for k =[   a   ] to [   b   ] step [   c   ]:
   A[k] = 0;
for k = 2 to 100 step 1:
  if A[k]≠0:
   print k;

H25h-問7
【正解】イ
実際のプログラムの例は以下
#include<stdio.h>   // stdio.h(標準入出力を行うための関数が定義されたファイル)を読み込む
// main関数。引数は取らない。処理後に値を返さない
void main() {
    int A[101];    // 配列変数Aを定義。保存可能個数は101個でA[0]-A[100]を使用可能。
    int k, m;  // 整数型の変数kとmを定義
    // kを2から100まで、1ずつ増やす(k++)
    for (k = 2; k <= 100; k++) {
        A[k] = 1;  // A[2]-A[100]をすべて1にしている
    }
    // 2の倍数-10の倍数をリストから消していく
    for (m = 2; m <= 10; m++) { // mを2から10まで1ずつ増やす
        for (k = 2*m; k <= 100; k += m) {
            // kを2mから100までmずつ増やす
            // つまりkは2m, 3m, 4m,・・・と変化
            A[k] = 0;  // kはmの倍数=素数ではないから0にする
        }
    }
    for (k = 2; k <= 100; k++) { // kを2から100まで1ずつ増やす
        if (A[k] != 0) {  // A[k]が0でない、つまりkが素数なら
            printf("%d,", k);  // kを表示
        }
    }
}
【処理の解説】
・エラトステネスのふるい法を使って素数を求めています。
・変数Aは、0か1の値になるが、A[k]=0なら非素数、A[k]=1なら素数(処理の途中では「素数の可能性」)
・まず2から100をすべて素数かもしれないリストに入れる
   (k=2-100についてA[k] = 1)
・素数とは「約数として自分と1だけもつ」ことから、「何かの倍数であれば素数ではない」という考えで、倍数をすべて消していく。具体的にはA[k] = 0

■H28春
問6 流れ図に示す処理の動作の記述として,適切なものはどれか。ここで,二重線は並列処理の同期を表す。
H28h-問6
ア ABC又はACBを実行してデッドロックになる。
イ AB又はACを実行してデッドロックになる。
ウ Aの後にBC又はCB,  BC又はCB,…と繰り返して実行する。
エ Aの後にBの無限ループ又はCの無限ループになる。
【正解】ウ

■H27春
問6 モンテカルロ法によって,正方形に内接する円の面積を近似的に求める方法はどれか。
ア 円に内接する正多角形の面積によって求める。
イ 正方形内に多数の小円を重ならないようにぎっしり詰めて,円の中にある小円の個数によって求める。
ウ 正方形内に乱数を用いて多数の点を一様に打ち,円の中にある点の個数によって求める。
工 正方形内を微細な間隔の格子点で区切り,円の中にある格子点の個数によって求める。
【正解】ウ

■H26春
問5 記憶領域を管理するアルゴリズムのうち,ベストフィット方式の特徴として,適切なものはどれか。
ア 空きブロック群のうち,アドレスが下位のブロックを高い頻度で使用するので,アドレスが上位の方に大きな空きブロックが残る傾向にある。
イ 空きブロック群のうち,要求された大きさを満たす最小のものを割り当てるので,最終的には小さな空きブロックが多数残る傾向にある。
ウ 空きブロックの検索にハッシュ関数を使用しているので,高速に検索することができる。
エ 空きブロックをアドレスの昇順に管理しているので,隣接する空きブロックを簡単に見つけられ,より大きな空きブロックにまとめることができる。
【正解】イ

アルゴリズムとは、「コンピュータに,ある特定の目的を達成させるための処理手順(H25春IP問53)」です。

アルゴリズムの用語として、以下があります。
・流れ図(フローチャート)

■過去問(H25春IP)
問53 コンピュータを利用するとき,アルゴリズムは重要である。アルゴリズムの説明として,適切なものはどれか。
ア:コンピュータが直接実行可能な機械語に,プログラムを変換するソフトウェア
イ:コンピュータに,ある特定の目的を達成させるための処理手順
ウ:コンピュータに対する一連の動作を指示するための人工言語の総称
エ:コンピュータを使って,建築物や工業製品などの設計をすること

正解はイです。
アはコンパイラ
ウはプログラム言語
エはCAD です。

過去問(H27秋AP午前問6)を見てみましょう。
問6 次に示すユークリッドの互除法(方法1,方法2)で,正の整数a, bの最大公約数は,それぞれmとnのどちらの変数に求まるか。ここで,mod nは,mをnで割った余りを表す。
flow
【正解】ウ

フローチャートに関して過去問(H27春IP問59)では、「プログラムの処理手順を図式を用いて視覚的に表したもの」と述べられています。

過去問(H27春IP問48)では、以下の流れ図があります。
問48 表に示す構成のデータを,流れ図の手順で処理する場合について考える。流れ図中のx,y,zをそれぞれデータ区分A, B, Cと適切に対応させれば,比較(“xか?”,“yか?”',“zか?”)の回数の合計は,最低何回で済むか。
流れず

ア 170  イ 190  ウ 230  工 250

平成29年春期 午前 問6
問6 次の流れ図の処理で,終了時のxに格納されているものはどれか。ここで,与えられたa,bは正の整数であり,mod(x,y)はxをyで割った余りを返す。

H29h-問6
ア aとbの最小公倍数
イ aとbの最大公約数
ウ aとbの小さい方に最も近い素数
エ aをbで割った商
実際に数字を入れてみるといいでしょう。
mod(x,y)はxをyで割った余りを返す。とありますから、xの方を大きくしましょう。
たとえば、a=10、b=3とします。
x=10、y=3

ループ1の1回目(y=0ではないので)
t=1(10÷3=3 余り1)
x=3
y=1

ループ1の2回目(y=0ではないので)
t=0
x=1
y=0
つまり、x=1であることが分かります。では、選択肢の4つを見ると
ア aとbの最小公倍数 ⇒30なので×
イ aとbの最大公約数 ⇒1なので○
ウ aとbの小さい方に最も近い素数 ⇒1なので○
エ aをbで割った商 ⇒3なので×
よって、イかウです。

イではないかとあたりをつけて、a=12、b=8、xが最大公約数である4になるかを確かめましょう。
たとえば、a=12、b=8とします。
x=12、y=8

ループ1の1回目(y=0ではないので)
t=4(12÷8=1 余り4)
x=8
y=4

ループ1の2回目(y=0ではないので)
t=0
x=4
y=0
と、xが最大公約数である4になりました。これは、選択肢ウのaとbの小さい方に最も近い素数である2とも違います。よって、イが正解です。

過去に似たような問題が出題されていますので、このアルゴリズムは最大公約数を求めるものだと覚えておくとよいでしょう。

【正解】イ
補足および実際のプログラムはこちら
http://sm.seeeko.com/archives/65924350.html

このページのトップヘ