第 13 回応用プログラミング復習用演習課題 2014/12/17 課題 1：二分

第 13 回応用プログラミング復習用演習課題
2014/12/17
課題 1：二分探索法
以下は，降順に並んだ int 型の配列 array から指定された要素 x を探すプログラムである．空欄に
適切なコードを記述せよ．
#include<iostream>
using namespace std;
int mybinary_search(const int array[], int x, int size){
int left = 0;
//配列の先頭の添字を設定
int right = size-1;
//配列の最後尾の添字を設定
while(left<=right){
int middle = (left+right)/2;
//現在の探索範囲の中央の添字を設定
if(array[middle]==x){ return middle; } //見つかったので添字を返す
if(array[middle]<x){ right = middle-1; } //xが中央の値よりも大きい場合．
else{ left = middle+1; }
//xが中央の値以下の場合．
}
return -1;
}
int main(void){
const int size =10;
const int array[size] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int x;
while( cout << Input an integer : && cin >> x){
if(mybinary_search(array, x, size)!=-1){ cout << x <<
else{ cout << x << is not found! << endl; }
}
return 0;
}
実行例（下線部はキーボードからの入力）
% ex1
Input an integer : 8
8 is found!
Input an integer : -4
-4 is not found!
Input an integer : ctrl+d
voidVoid
is found! << endl; }
課題 2：バブルソート
以下は，バブルソートを用いて降順に並び替えるプログラムである．空欄に適切なコードを記述せ
よ．
#include<iostream>
#include<algorithm>
using namespace std;
void print(int array[], int size){
for(int i=0; i<size; i++){
cout << array[i] << ;
}
cout << endl;
}
void bubble_sort(int array[], int size){
for(int i=0; i< size-1; i++){
for(int j=0; j < size-i-1; j++){
if(array[j] < array[j+1]){
swap(array[j], array[j+1]);
}
}
}
}
//配列の表示用の関数
//バブルソート（降順）の関数
int main(void){
const int size=10;
int array[size] = {6, 4, -3, -5, 3, 8, 0, -2, 9, 1};
print(array, size);
bubble_sort(array, size);
print(array, size);
return 0;
}
実行例（下線部はキーボードからの入力）
% ex2
6 4 -3 -5 3 8 0 -2 9 1
9 8 6 4 3 1 0 -2 -3 -5
課題 3：選択ソート
以下は，選択ソートを用いて降順に並び替えるプログラムである．空欄に適切なコードを記述せよ．
#include<iostream>
#include<algorithm>
using namespace std;
void print(int array[], int size){
for(int i=0; i<size; i++){
cout << array[i] << ;
}
cout << endl;
}
//配列の表示用の関数
void selection_sort(int array[], int size){
//選択ソート（降順）の関数
for(int i=0; i< size-1; i++){
int max= i;
//最大値を探す．探索範囲の先頭の添字を設定．
for(int j=i+1; j<size; j++){
if(array[max]<array[j]){ max = j;}
//最大値を保持する配列の添字を更新．
}
swap(array[i], array[max]);
//探索範囲の先頭の要素と交換
}
}
int main(void){
const int size=10;
int array[size] = {6, 4, -3, -5, 3, 8, 0, -2, 9, 1};
print(array, size);
selection_sort(array, size);
print(array, size);
return 0;
}
実行例（下線部はキーボードからの入力）
% ex3
6 4 -3 -5 3 8 0 -2 9 1
9 8 6 4 3 1 0 -2 -3 -5
課題 4：ライブラリ関数の利用
以下は，<algorithm>ヘッダファイルの sort 関数と binary_search 関数を利用し，配列内に指定さ
れた x が存在するかどうかを判定するプログラムである．空欄に適切なコードを記述せよ．
#include<iostream>
#include<algorithm>
using namespace std;
void print(int array[], int size){
for(int i=0; i<size; i++){
cout << array[i] << ;
}
cout << endl;
}
int main(void){
const int size=10;
int array[size] = {6, 4, -3, -5, 3, 8, 0, -2, 9, 1};
print(array, size);
sort(&array[0], &array[size]);
//sort関数を呼び出す．
print(array,size);
int x;
while( cout << Input an integer : && cin >> x){
if(binary_search(&array[0], &array[size], x)){ //binary_search関数を呼び出す．
cout << x << is found! << endl;
}
else{ cout << x << is not found! << endl; }
}
return 0;
}
実行例（下線部はキーボードからの入力）
% ex4
6 4 -3 -5 3 8 0 -2 9 1
-5 -3 -2 0 1 3 4 6 8 9
Input an integer : 8
8 is found!
Input an integer : -4
-4 is not found!
Input an integer : ctrl+d

Download Report