東京工芸大学 工学部  電子機械学科 2年 前期 

基礎プログラミング 第9回
 2017.6.6 
藤木 文彦

http://fujiki.tv/t-kougei/kisoprog/
fujiki.kougei@gmail.com  



※ 先週の最後に掲げた課題とは、Project 番号が違っていますから注意。

  1.配列への初期データの入力


まず、入力プログラムだけを動作確認してみましょう。
これは、順にデータ(正の実数)を入力し、入力されたデータを表示する物です。

データの入力終了時には、 −1 を入力します。

 何回繰り返すかがあらかじめ決まっていなくて、ある条件が満たされたら(ある値が入力されたら)終了する、というような場合には、次のような  while 文、または do while 文を用います。いつの時点で繰り返しを終わるかによって、使い分けます。

   while( 条件 ){
   処理
  }


または

   do{
   処理
  } while( 条件 );


 条件が満たされているあいだ、処理を繰り返します。
 どちらも、途中で終了するためには、

 if( 条件 ){
   break;
 }


を入れることにより、ループの外に脱出します。

  (例題1) 

Project0901

#include "stdafx.h"


#include "iostream"
#include "string"
using namespace std;

#define LIMIT 100

int _tmain(int argc, _TCHAR* argv[])
{

	int i, num = 0;
	int a[LIMIT];
	while (num<LIMIT){
		printf("Input number( END=-1) %d: ", num);
		cin >> a[num];
		printf("\n");
		if (a[num] == -1){
			break;
		}
		num++;
	}
	for (i = 0; i<num; i++){
		printf("\n%d: %d ", i, a[i]);
	}
	printf("\n");


	getchar();//2回書く
	getchar();
	return 0;
}


 【演習問題1】 

 上記プログラムで、入力された値が、−999 ならば終了するようにしなさい。また、最後に、入力されたデータの 「個数、合計、平均値」を出力するようにしなさい。

  2.単純比較法


まず、あらかじめデータが決められている場合について実行してみます。

この方法は、
 1番はじめの項目と、2番目以降を全部比べ、一番小さいものを1項目目に持ってくる。
 2番目の項目と、3番目以降を全部比べ、一番小さいものを2項目目に持ってくる。
 3番目以降も同様に、全部の個数−1 まで繰り返すと、小さい順に並んでいる。
というものです。

  (例題2) 

Project0902

#include "stdafx.h"

#define MAX 10
int x[] = { 9, 4, 6, 2, 1, 8, 0, 3, 7, 5 };

void PrintData(int x[], int n, int m);
void ConvSort(int x[], int n);

int _tmain(int argc, _TCHAR* argv[])
{
	printf("Before:\n");
	PrintData(x, MAX, MAX);
	printf("\n");

	ConvSort(x, MAX);

	printf("After:\n");
	PrintData(x, MAX, MAX);
	printf("\n");
	getchar();
	return 0;

}

void PrintData(int x[], int n, int m)
{
	int i;

	for (i = 0; i < m; i++){
		printf("%3d", x[i]);
		if (i == n){
			printf(" - ");
		}
	}
	printf("\n");
}

void ConvSort(int x[], int n)
{
	int i, j, temp;

	for (i = 0; i < n - 1; i++) {
		for (j = i; j <n; j++) {
			if (x[j] < x[i]) {
				temp = x[j];
				x[j] = x[i];
				x[i] = temp;
			}
		}
		PrintData(x, i, MAX);
	}
}

実行結果の表示が次のように出れば成功です。



 【演習問題2】 

 上記プログラムを書き換えて、左端が一番大きくなるように並べるようにしなさい。


  3.バブルソート


 並んだ配列の、隣り合った2つの内容を比べて、小さいほうが左に来るようにしながら、順次入れ替えていく方法です。
1回行うと、大小関係が逆転している部分が、全て入れ替わりますが、まだ、最小値が一番左には来ていませんので、同じことを配列の個数分−1回繰り返して行います。
すると、一番小さいものが一番左へ、以下大きさの順に並び、一番大きいものが右に来ます。
 水面に底から泡(バブル)が上がってくるように、少しずつ小さい値が左側に移動していくので、バブルソートといいます。

  (例題3) 


●の部分は、2つの配列を入れ替える部分です。自分で考えて書きなさい。

Project0903

#include "stdafx.h"
	void bubSort(int num[], int n);
	void printData(int num[], int n);
#define MAX 10
	int x[] = { 9, 4, 6, 2, 1, 8, 0, 3, 7, 5 };

	int _tmain(int argc, _TCHAR* argv[])
	{
		printf("Before:\n");
		printData(x, MAX);
		printf("\n");

		bubSort(x, MAX);

		printf("After:\n");
		printData(x, MAX);
		printf("\n");

		getchar();
		return 0;
	}
	void printData(int x[], int n)
	{
		int i;

		for (i = 0; i < n; i++)
			printf("%-3d", x[i]);
		printf("\n");
	}

	void bubSort(int x[], int n)
	{
		int i, j, temp;

		for (i = 0; i < n - 1; i++) {
			for (j = n - 1; j > i; j--) {
				if (x[j - 1] > x[j]) {
					temp = x[j];
					●
					x[j - 1] = temp;
				}
			}
			printData(x, MAX);
		}
	}





実行結果




 【演習問題3】 

 上記プログラムを変更して、左端が一番大きくなるようにしなさい。



  4.単純挿入ソート(1)

 並んでいるデータの中から一番小さいものを左に持ってくる、ということを繰り返す方法です。
左側に何個かのデータが(既に)大きさの順に並んでいるとします。

 小 大   不揃い
 ○○○  △×××
        △を入れる場所を探す

 △より大きいものを右にずらす
     →→
 ○ △ ○○  ×××
   △より小さいものが見つかったら、その位置に△を入れる。
  
 詳しい動作は、プログラムを入力してから説明します。

  (例題4) 


Project0904

   


#define MAX 8

void InsSort(int num[], int n);
void PrintData(int num[], int n);


void InsSort(int num[], int n)
{
	int i, j, temp;

	for (i = 1; i < n; i++) {

		temp = num[i];

		for (j = i; j > 0 && num[j - 1] > temp; j--){
			num[j] = num[j - 1];
		}
			num[j] = temp;
		PrintData(num, MAX);
	}
}


void PrintData(int num[], int n)
{
	while (n--)
		printf("%d ", *num++);
	printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{

	int num[] = { 3, 7, 1, 5, 4, 2, 6, 0 };


	printf("Before:\n");
	PrintData(num, MAX);
	printf("\n");


	InsSort(num, MAX);
	printf("\n");


	printf("After:\n");
	PrintData(num, MAX);
	printf("\n");

	getchar();
	return 0;

      
}


実行結果の表示が次のように出れば成功です。


Before:
3 7 1 5 4 2 6 0

3 7 1 5 4 2 6 0
1 3 7 5 4 2 6 0
1 3 5 7 4 2 6 0
1 3 4 5 7 2 6 0
1 2 3 4 5 7 6 0
1 2 3 4 5 6 7 0
0 1 2 3 4 5 6 7

After:
0 1 2 3 4 5 6 7

 【演習問題4】 

 上記プログラムを変更して、左端が一番大きくなるようにしなさい。

  5.単純挿入ソート(2)

 前の問題の動作をもう一度確認します。
 具体的な動作としては、次のようになります。


Before:
55 33 66 11 44 22    最初は 1番目を1番目と比較−>何もしない

33 55 
66 11 44 22    最初の2項目だけ考え、後は考えない
33 55 66 
11 44 22    最初の3項目だけ考え、後は考えない
11 33 55 66 
44 22    以下同様
11 33 44 55 66 22
11 22 33 44 55 66
After:
11 22 33 44 55 66





Before:
55 33 66 11 44 22    55 は、自分自身と比較しても何も起こらない。 
                次候補 33 を取る。 前の列(今は55だけ)と比較すると、
                前のほうが大きいので、前にある55を右にずらす。
33 55 66 11 44 22    次候補66をとる
                前候補55よりも、33よりも大きいのでなにも起こらない。

33 55 66 11 44 22    次候補11をとる。
                前の66より小さいので、66を右にずらす。
                その前の55より小さいので、55も右にずらす。
                その前の33より小さいので、33も右にずらす。
                先頭まで来たので、そこに11を入れる。
11 33 55 66 44 22    次候補44をとる。
                66,55より小さいので、それを右にずらす。
                33より大きいので、33は置いたまま、その右に44を入れる。
                55はすでにずれているので、上書きしても構わない。

11 33 44 55 66 22    22を次候補とする。
                66,55,44、33より小さいので、これらを右にずらす。
                11よりおおきいので、それは置いたまま、その右に22を入れる。
11 22 33 44 55 66    並べ替え完成

After:
11 22 33 44 55 66


 前の問題と同じことを再度プログラムしますが、数値の入力をキーボードからできるようにします。

  (例題5) 


Project0905

#include "stdafx.h"


#include "iostream"
#include "string"
using namespace std;

#define MAX 100
int x[MAX];


void InputData(int a[], int *m) // *m の * に注意
{
	int i;
	while (*m<MAX){ // *m に注意
		printf("Input number( END=-1) %d: ", *m); // 同上
		cin >> a[*m]; // 同上
		if (a[*m]<0){ // 同上
			break;
		}
		(*m)++; // 同上
	}

	for (i = 0; i<*m; i++){ // 同上

		printf("%d \n", a[i]);
	}
	printf("\n");

}

void PrintData2(int x[], int n)
{
	int i;

	for (i = 0; i < n; i++){
		printf("%d ", x[i]);
	}
	printf("\n");
}

void InsSort(int num[], int n)
{
	int i, j;
	int tmp;

	for (i = 1; i < n; i++) {

		tmp = num[i];

		for (j = i; j > 0 && num[j - 1] > tmp; j--){
			num[j] = num[j - 1];
		}
		num[j] = tmp;
		PrintData2(num, n);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	do{
		int num = 0;
		int a[MAX];
		InputData(a, &num); // & に注意
		printf("Before:\n");
		PrintData2(a, num);
		printf("\n");
		InsSort(a, num);

		printf("After:\n");
		PrintData2(a, num);

		printf("Continue= [Enter] END = [q] ");

		getchar();
	} while (getchar() != 'q');
	return 0;
}


 【演習問題5】 

 上記プログラムを変更して、左端が一番大きくなるようにしなさい。



  6.マージソート


2つのグループに分けられている数値の組から、それぞれ、先頭をとり、小さいほうを取り出して、配列に並べていく方法です。
 ただし、その数値の組は、あらかじめ大きさの順に並んでいるものとします。
 もちろん、あらかじめ2つのグループがそれぞれ大きさの順に並んでいるとは限りません。
 そのため、再帰法という方法を用います。

 「マージ」とは、混ぜる、という意味です。

次のプログラムを打ち込んで動作させて見てください。動きの説明は複雑なので、教室で行います。

  (例題6) 


Project0906

      
#include "stdafx.h"


#define MAX_DATA 10

int temp[MAX_DATA];

void MergeSort(int x[], int left, int right);
void main(void);

void MergeSort(int x[], int left, int right)
{
	int mid, i, j, k;

	if (left >= right)
		return;
	mid = (left + right) / 2;
	MergeSort(x, left, mid);
	MergeSort(x, mid + 1, right);

	for (i = left; i <= mid; i++)
		temp[i] = x[i];

	for (i = mid + 1, j = right; i <= right; i++, j--){
		temp[i] = x[j];
	}
	i = left;
	j = right;

	for (k = left; k <= right; k++){
		if (temp[i] <= temp[j]) {
			x[k] = temp[i++];
		}
		else{
			x[k] = temp[j--];
		}
	}
}



int _tmain(int argc, _TCHAR* argv[])
{
	int i;
	int x[] = { 9, 4, 6, 2, 1, 8, 0, 3, 7, 5 };

	printf("Before:\n");
	for (i = 0; i < MAX_DATA; i++)
		printf("%d\t", x[i]);

	MergeSort(x, 0, MAX_DATA - 1);

	printf("After:\n");
	for (i = 0; i < MAX_DATA; i++)
		printf("%d\t", x[i]);
	printf("\n");

	getchar();
	return 0;
}



実行結果が次のようになれば成功です


Before:
9 4 6 2 1 8 0 3 7 5
After:
0 1 2 3 4 5 6 7 8 9 

 【演習問題6】 

 上記プログラムは変更しなくて良いので、動作したら、そのプログラムをメールに添付して報告しなさい。

  7.クイックソート


 並べられた数値を、適当なを決めて、それより大きいグループと小さいグループに分けます。それぞれのグループ内での並び順は問いません。

 次に、そうやって分けられたグループのそれぞれについて、上記と同様にして、その中の数値を、2グループに分けます。
 そうすると、次第に小さい数値のグループが一番左に、大きい数値のグループが右に並ぶようになります。
 この作業は、再帰的に行い、グループ内の数値の数が1つになったら、もう分ける必要が無いので、それを呼び出したところに戻ります。
 この操作は図面を書いて説明します。

  (例題7) 


Project0907


  
#include "stdafx.h"


#include "iostream"
#include "string"
using namespace std;

#define MAX 100
int x[MAX];
void QSort(int x[], int left, int right);
void Swap(int x[], int i, int j);
void PrintData(int x[], int n);
void main(void);

void QSort(int x[], int left, int right)
{
	int i, j;
	int pivot;

	i = left;
	j = right;

	pivot = x[(left + right) / 2];

	while (1) {

		while (x[i] < pivot)
			i++;

		while (pivot < x[j])
			j--;
		if (i >= j)
			break;

		Swap(x, i, j);
		i++;
		j--;
	}
	PrintData(x, 10);

	if (left < i - 1)
		QSort(x, left, i - 1);
	if (j + 1 < right)
		QSort(x, j + 1, right);
}

void Swap(int x[], int i, int j)
{
	int temp;

	temp = x[i];
	x[i] = x[j];
	x[j] = temp;
}


void PrintData(int x[], int n)
{
	int i;

	for (i = 0; i < n; i++)
		printf("%d ", x[i]);
	printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	int x[] = { 6, 3, 1, 7, 0, 4, 8, 5, 2, 9 };
	int n = 10;

	printf("Before:\n");
	PrintData(x, n);

	printf("Progress:\n");
	QSort(x, 0, n - 1);

	printf("After:\n");
	PrintData(x, n);

	getchar();
	return 0;
}









Before:
6 3 1 7 0 4 8 5 2 9
Progress:
0 3 1 7 6 4 8 5 2 9
0 3 1 2 4 6 8 5 7 9
0 1 3 2 4 6 8 5 7 9
0 1 2 3 4 6 8 5 7 9
0 1 2 3 4 6 8 5 7 9
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
After:
0 1 2 3 4 5 6 7 8 9


 【演習問題7】 

 上記プログラムは、変更しなくて良いので、きちんと動作するようになったら、それを報告しなさい。