0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Yuta_Nakamura_(Yuta Nakamura)

書籍 ダイテル C言語プログラミング 練習問題 解答 6章

0
Last updated at Posted at 2026-04-26
書籍

image.png

6.10: 週給が各範囲(200-299ドル、300-399ドル、...)に該当する販売員の人数を求めるプログラム
source
#include <stdio.h>
#include <conio.h>

#define RANGE 11

void input_data(int [],int);
void print_list(int [],int);

int main()
{   
    static int list[RANGE];
    int count;


    printf("何人分のデータを入力しますか?\n");
    scanf("%d",&count);
   
    input_data(list,count);
  
    print_list(list,RANGE);

    
    getch();
    return 0;
}

void input_data(int list[],int count)
{
    double sales;
    double week_wage;

     while(--count>=0)
    { 
        printf("この従業員は週に何ドル売り上げましたか?\n");
        scanf("%lf",&sales);

        sales*=0.09;
        week_wage=200+sales;

        list[(int)(week_wage/100)]++;
    }
}

void print_list(int list [],int range)
{
    int i;
    int count=0;

    for(i=2;i<=9;i++)
    { 
          printf("%5d-%5dドル %3d人\n",i*100,i*100+99,list[i]);
    }
    
    for(i=10;i<=range;i++)
    {
       count+=list[i];
    }
    printf("  1000ドル以上 %3d人\n",count);
    
    return;
}
6.11: バブルソートの改良
  • a: 最初のパスが終わると、最も大きな値が最後の配列に格納される。2回目のパスが終わると、2番目に大きな値が最後の1つ手前の配列要素に格納される。以下同様。全てのパスで配列のサイズ分比較する代わりに、2回目のパスでは配列のサイズ分 - 1、3回目のパスでは配列のサイズ分 - 2、... 比較するよう改良
source
#include <stdio.h>
#include <conio.h>

#define SIZE 10

int main()
{
    int a[SIZE]={2,6,4,8,10,12,89,68,45,36};
    int i,pass,hold;

    printf("元のデータの項目の順序\n");

    for(i=0;i<=SIZE-1;i++)
    {
       printf("%4d",a[i]);
    }
    printf("\n\n");

    for(pass=1;pass<=SIZE-1;pass++)
    {
       for(i=1;i<=SIZE-pass-1;i++)
       {
          if(a[i]>a[i+1])
          {
             hold=a[i];
             a[i]=a[i+1];
             a[i+1]=hold;
          }
       }
       for(i=0;i<=SIZE-1;i++)
       {
          printf("%4d",a[i]);
       }
       printf("\n");
    }

    printf("\n昇順にソートしたデータ項目\n");
 
    for(i=0;i<=SIZE-1;i++)
    {
       printf("%4d",a[i]);
    }
    printf("\n");
    getch();
    return 0;
}
  • b: 交換が行われたかどうかを各パスの終わりでチェックするように改良(交換が行われなかった場合データはすでに正しい順序で並んでいるので、その時点でソートを終了してよい)
source
#include <stdio.h>
#include <conio.h>

#define SIZE 10
int main()
{
    int a[SIZE]={2,6,4,8,10,12,89,68,45,36};
    int i,pass,hold;
    int swap;

     printf("元のデータの項目の順序\n");

    for(i=0;i<=SIZE-1;i++)
    {
       printf("%4d",a[i]);
    }

    printf("\n");
    do
    {  
       swap=0;

       for(i=0;i<SIZE-1;i++)
       {
        if(a[i]>a[i+1])
        {
           hold=a[i];
           a[i]=a[i+1];
           a[i+1]=hold;
           swap=1;
        }
       }
    }
    while(swap!=0);

    printf("\n昇順にソートしたデータ項目\n");
 
    for(i=0;i<=SIZE-1;i++)
    {
       printf("%4d",a[i]);
    }
    printf("\n");
    getch();
    return 0;
}
6.14: 関数modeが同点の最頻値を処理できるようにしたプログラム(リスト6.14(P.205)のプログラムを改良)、また、偶数個の要素をもつ配列の場合、真ん中の2つの要素の平均をとるよう関数medianを変更したプログラム
source
#include <stdio.h>
#include <string.h>  // memcpy用

#define SIZE 99
#define MODE_NUM 10

void mean(int []);
void median(int []);
void mode(int [], int []);
void bubblesort(int []);
void printArray(int []);

int main(void)
{
    int frequency[10] = {0};
    int response[SIZE] = {
        6,7,8,9,8,7,8,9,8,9,
        7,8,9,5,9,8,7,8,7,8,
        6,7,8,9,3,9,8,7,8,7,
        7,8,9,7,9,8,9,7,8,9,
        6,7,8,7,7,7,9,8,9,2,
        7,8,9,8,9,8,9,7,5,3,
        5,6,7,2,5,3,9,4,6,4,
        7,8,9,6,8,7,8,9,7,8,
        7,4,4,2,5,3,8,7,5,6,
        4,5,6,1,6,5,7,8,7
    };

    mean(response);
    median(response);
    mode(frequency, response);

    return 0;
}

/* 平均値 */
void mean(int answer[])
{
    int j, total = 0;

    printf("%s\n%s\n%s\n", "***********", "   平均値", "***********");

    for (j = 0; j < SIZE; j++)   // ← 修正（<= → <）
    {
        total += answer[j];
    }

    printf("平均値はデータ項目の各値を算術平均したもの\n"
           "つまり,全データ項目の値の合計をデータ項目の\n"
           "個数(%d)で割った値に等しい\n"
           "この場合の平均は: %d / %d = %.4f\n\n",
           SIZE, total, SIZE, (float)total / SIZE);
}

/* 中央値 */
void median(int answer[])
{
    int temp[SIZE];  // ← コピー用

    printf("\n%s\n%s\n%s\n%s",
           "***************", "  中央値", "***************",
           "未ソート配列は");

    printArray(answer);

    /* 配列コピーしてからソート */
    memcpy(temp, answer, sizeof(temp));
    bubblesort(temp);

    printf("\n\nソートされた配列は");
    printArray(temp);

    if (SIZE % 2 == 1)  // 奇数
    {
        printf("\n\n中央値はサイズ %d のソートされた配列の要素 %d\n"
               "この場合の中央値は %d\n\n",
               SIZE, SIZE / 2, temp[SIZE / 2]);
    }
    else  // 偶数
    {
        double med = (temp[SIZE/2] + temp[SIZE/2 - 1]) / 2.0;  // ← 修正（浮動小数）
        printf("\n\n中央値はサイズ %d の中央2要素の平均\n"
               "この場合の中央値は %.2f\n\n",
               SIZE, med);
    }
}

/* 最頻値（複数対応） */
void mode(int freq[], int answer[])
{
    int rating, j, h, largest = 0;
    int modeValue[MODE_NUM];
    int mode_num = 0;

    printf("\n%s\n%s\n%s\n",
           "***************", " 最頻値", "***************");

    /* 初期化 */
    for (rating = 1; rating <= 9; rating++)
    {
        freq[rating] = 0;
    }

    /* 出現回数カウント */
    for (j = 0; j < SIZE; j++)
    {
        ++freq[answer[j]];
    }

    printf("%s%11s%21s\n\n",
           "回答", "出現回数", "ヒストグラム");

    for (rating = 1; rating <= 9; rating++)
    {
        printf("%4d%11d        ", rating, freq[rating]);

        if (freq[rating] > largest)
        {
            largest = freq[rating];
            mode_num = 0;
            modeValue[mode_num++] = rating;
        }
        else if (freq[rating] == largest)
        {
            modeValue[mode_num++] = rating;
        }

        for (h = 0; h < freq[rating]; h++)
        {
            printf("*");
        }
        printf("\n");
    }

    printf("\n最頻値（複数可）:\n");
    for (j = 0; j < mode_num; j++)
    {
        printf("%d (出現回数: %d 回)\n", modeValue[j], largest);
    }
}

/* バブルソート */
void bubblesort(int a[])
{
    int pass, j, hold;

    for (pass = 0; pass < SIZE - 1; pass++)
    {
        for (j = 0; j < SIZE - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                hold = a[j];
                a[j] = a[j + 1];
                a[j + 1] = hold;
            }
        }
    }
}

/* 配列表示 */
void printArray(int a[])
{
    int j;

    for (j = 0; j < SIZE; j++)
    {
        if (j % 20 == 0)
        {
            printf("\n");
        }
        printf("%2d ", a[j]);
    }
    printf("\n");
}
6.15: 10以上100以下の数値を20回読み込み、数値を1個読み込むたびに、その数値がすでに読み込んだ数値と重複しているかどうかをチェックし、重複してないときだけプリントするプログラム
source
#include <stdio.h>

#define SIZE 20

int main(void)
{
    int data;
    int check[SIZE];
    int count = 0;  // 保存済みのユニーク数

    for(int i = 0; i < SIZE; i++)
    {
        // 入力（10〜100制約）
        do
        {
            printf("%2d回目: 10〜100の整数を入力してください: ", i + 1);
            scanf("%d", &data);
        } while(data < 10 || data > 100);

        // 重複チェック
        int j;
        for(j = 0; j < count; j++)
        {
            if(check[j] == data)
            {
                break;
            }
        }

        // 重複していなければ表示＆保存
        if(j == count)
        {
            printf("  -> %d は新規データです\n", data);
            check[count] = data;
            count++;
        }
    }

    return 0;
}
6.19: 2個のサイコロ振りをシミュレートするプログラム
source
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TRIAL 36000
#define SIZE 13

int dice(void);
int two_dice(void);

int main()
{   
    int i;
    int result;
    static unsigned list[SIZE];
    
    srand(time(NULL));

    for(i=0;i<TRIAL;i++)
    { 
       result=two_dice();
       list[result]++;
    }

    for(i=2;i<SIZE;i++)
    {
       printf("%3dの出現回数%5d\n",i,list[i]);
    }
    return 0;
}

int dice()
{
   return rand()%6+1;
}

int two_dice()
{
   return dice()+dice();
}
6.20: クラップスゲームを1000回走らせるプログラム
source
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define P_WIN 1
#define P_LOSE 0

#define GAME 1000

int rollDice(void);
int game(void);

int main()
{
    int i=0;
    int p_win=0;

    srand(time(NULL));

    while(i<GAME)
    {

       if(game()==P_WIN)
       {
          p_win++;
       }
       i++;
    }
    printf("%d回勝ちました\n",p_win);
    printf("%d回負けました\n",GAME-p_win);
    printf("勝率%lf%%\n",(double)p_win/GAME*100);
    return 0;
}

int rollDice()
{
    int di1,di2,workSum;
  
    di1=1+(rand()%6+1);
    di2=1+(rand()%6+1);
    workSum=di1+di2;
    
    printf("プレイヤーがサイコロを振った　出目は %d+%d=%d\n",
            di1,di2,workSum);
    return workSum;
}

int game()
{ 
    int gameStatu,sum,myPoint;

    sum=rollDice();

    switch(sum)
    {
       case 7: 
       case 11:
         gameStatu=1;
         break;

       case 2:
       case 3:
       case 12:
         gameStatu=2;
         break;

       default:
         gameStatu=0;
         myPoint=sum;
         printf("もち点は  %d\n",myPoint);
         break;

    }

    while(gameStatu==0)
    {
        sum=rollDice();
      
        if(sum==myPoint)
        {
           gameStatu=1;
        }
        else
        {
           if(sum==7)
           {
              gameStatu=2;
           }
        }
    }

    if(gameStatu==1)
    {
       printf("プレイヤーの勝ち\n");
       return P_WIN;
    }
    else
    {
       printf("プレイヤーの負け\n");
       return P_LOSE;
    }
}
6.21: 航空座席予約システム
source
#include <stdio.h>

#define FREE 0
#define RESERVED 1

#define END      0
#define SMOKE    1
#define NO_SMOKE 2

#define SEAT_SIZE 11

int menu(void);
void reserve(int [], int);
void print_ticket(int seat_no, int type);   // 追加

int main()
{
    static int seat[SEAT_SIZE];
    int select;

    while(1)
    {
        select = menu();

        if(select == END)
        {
            break;
        }
        else if(select == SMOKE)
        {
            reserve(seat, SMOKE);
        }
        else
        {
            reserve(seat, NO_SMOKE);
        }
    }
    return 0;
}

int menu(void)
{
    int select;

    do
    {
        printf("喫煙席を希望する方は1をタイプしてください\n");
        printf("禁煙席を希望する方は2をタイプしてください\n");
        printf("入力を終了するならば0をタイプしてください\n");
        scanf("%d", &select);
    }
    while(select < 0 || 2 < select);

    return select;
}

/* 搭乗券を表示する関数 */
void print_ticket(int seat_no, int type)
{
    printf("\n===== 搭乗券 =====\n");

    if(type == SMOKE)
    {
        printf("区画 : 喫煙席\n");
    }
    else
    {
        printf("区画 : 禁煙席\n");
    }

    printf("座席番号 : %d\n", seat_no);
    printf("==================\n\n");
}

void reserve(int seat[], int type)
{
    int i;
    int yes_no;

    if(type == SMOKE)
    {
        for(i = 1; i <= 5; i++)
        {
            if(seat[i] == FREE)
            {
                seat[i] = RESERVED;
                printf("%d座席を予約しました\n", i);

                print_ticket(i, SMOKE);   // 搭乗券表示
                break;
            }
        }

        if(i > 5)
        {
            printf("喫煙席は満杯です\n");
            printf("禁煙席でよろしいでしょうか?\n");
            printf("1 YES 0 NO\n");
            scanf("%d", &yes_no);

            if(yes_no == 0)
            {
                printf("3時間後に次のフライトがあります\n");
            }
            else
            {
                for(i = 6; i <= 10; i++)
                {
                    if(seat[i] == FREE)
                    {
                        seat[i] = RESERVED;
                        printf("%d座席を予約しました\n", i);

                        print_ticket(i, NO_SMOKE); // 搭乗券表示
                        break;
                    }
                }

                if(i > 10)
                {
                    printf("座席を確保することができませんでした\n");
                }
            }
        }
    }
    else
    {
        for(i = 6; i <= 10; i++)
        {
            if(seat[i] == FREE)
            {
                seat[i] = RESERVED;
                printf("%d座席を予約しました\n", i);

                print_ticket(i, NO_SMOKE); // 搭乗券表示
                break;
            }
        }

        if(i > 10)
        {
            printf("禁煙席は満杯です\n");
            printf("喫煙席でよろしいでしょうか?\n");
            printf("1 YES 0 NO\n");
            scanf("%d", &yes_no);

            if(yes_no == 0)
            {
                printf("3時間後に次のフライトがあります\n");
            }
            else
            {
                for(i = 1; i <= 5; i++)
                {
                    if(seat[i] == FREE)
                    {
                        seat[i] = RESERVED;
                        printf("%d座席を予約しました\n", i);

                        print_ticket(i, SMOKE); // 搭乗券表示
                        break;
                    }
                }

                if(i > 5)
                {
                    printf("座席を確保することができませんでした\n");
                }
            }
        }
    }
    return;
}
6.22: 先月の売上を記録したすべての伝票の情報を読み込んで、各販売員ごと、および各製品ごとの総売上高をプリントするプログラム
source
#include <stdio.h>
#include <conio.h>

#define PRODUCT 5
#define EMPLOYEE 4

void input_data(int [][PRODUCT]);
void print_data(int [][PRODUCT], int, int);

int main(void)
{
    int sales[EMPLOYEE][PRODUCT] = {0};

    input_data(sales);
    print_data(sales, EMPLOYEE, PRODUCT);

    getch();
    return 0;
}

void input_data(int s[][PRODUCT])
{
    int day;
    int num;
    int em;
    int pro;
    int sale;

    printf("先月は何日ありましたか\n");
    scanf("%d", &day);

    while (day-- > 0)
    {
        printf("今日の伝票は何枚ありますか\n");
        scanf("%d", &num);

        while (num-- > 0)
        {
            printf("販売員番号を入力してください(1～%d)\n", EMPLOYEE);
            scanf("%d", &em);

            if (em < 1 || em > EMPLOYEE)
            {
                printf("販売員番号エラー\n");
                continue;
            }

            printf("製品番号を入力してください(1～%d)\n", PRODUCT);
            scanf("%d", &pro);

            if (pro < 1 || pro > PRODUCT)
            {
                printf("製品番号エラー\n");
                continue;
            }

            printf("売上高を入力してください\n");
            scanf("%d", &sale);

            s[em - 1][pro - 1] += sale;
        }
    }
}

void print_data(int s[][PRODUCT], int line, int row)
{
    int i, j;
    int sum_r[PRODUCT] = {0};
    int sum_l;
    int sum = 0;

    printf("\n先月の集計結果\n\n");
    printf("      1    2    3    4    5   合計\n");

    for (i = 0; i < line; i++)
    {
        sum_l = 0;

        printf("%2d ", i + 1);

        for (j = 0; j < row; j++)
        {
            printf("%4d ", s[i][j]);

            sum_l += s[i][j];
            sum_r[j] += s[i][j];
        }

        printf("%4d\n", sum_l);
    }

    printf("計 ");

    for (j = 0; j < row; j++)
    {
        printf("%4d ", sum_r[j]);
        sum += sum_r[j];
    }

    printf("%4d\n", sum);
}
6.23: タートルグラフィックス
source
#include <stdio.h>
#include <conio.h>

#define LINE 50
#define ROW 50
#define INPUT_MAX 100
#define ERROR 0

/* ペンの状態 */
#define PEN_UP   1
#define PEN_DOWN 0

/* ペンの進行方向 */
#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3

typedef struct pen
{
    int x;
    int y;
    int state;
    int direction;
} PEN;

void init_array(int [][ROW], int, int);
void init_pen(PEN *);

void menu_print(void);
int input_command(int *);

void print_array(int [][ROW], int, int);

void pen_move(int [][ROW], int, int, PEN *, int);

void print_pen_state(PEN *);

int main(void)
{
    int array[LINE][ROW];
    PEN pen;

    int move = 0;
    int end_flag = 0;
    int op;

    init_array(array, LINE, ROW);
    init_pen(&pen);

    while (!end_flag)
    {
        menu_print();

        op = input_command(&move);

        switch (op)
        {
            case 1:
                printf("ペンアップしました\n");
                pen.state = PEN_UP;
                break;

            case 2:
                printf("ペンダウンしました\n");
                pen.state = PEN_DOWN;
                break;

            case 3:
                printf("右に曲がります\n");
                pen.direction = (pen.direction + 1) % 4;
                break;

            case 4:
                printf("左に曲がります\n");
                pen.direction = (pen.direction + 3) % 4;
                break;

            case 5:
                printf("前方に%d歩進みます\n", move);
                pen_move(array, LINE, ROW, &pen, move);
                break;

            case 6:
                printf("配列をプリントします\n");
                print_array(array, LINE, ROW);
                break;

            case 8:
                print_pen_state(&pen);
                break;

            case 9:
                printf("データ終了\n");
                end_flag = 1;
                break;

            default:
                printf("入力が不正です\n");
        }
    }

    getch();
    return 0;
}

/* ペン初期化 */
void init_pen(PEN *p)
{
    p->state = PEN_UP;
    p->direction = NORTH;

    p->x = ROW / 2;
    p->y = LINE / 2;
}

/* 配列初期化 */
void init_array(int p[][ROW], int line, int row)
{
    int i, j;

    for (i = 0; i < line; i++)
    {
        for (j = 0; j < row; j++)
        {
            p[i][j] = 0;
        }
    }
}

/* コマンド入力 */
int input_command(int *move)
{
    char buf[INPUT_MAX];

    int op;
    int m;

    fgets(buf, sizeof(buf), stdin);

    if (sscanf(buf, "%d,%d", &op, &m) == 2)
    {
        if (op == 5)
        {
            *move = m;
            return 5;
        }
    }

    if (sscanf(buf, "%d", &op) == 1)
    {
        switch (op)
        {
            case 1:
            case 2:
            case 3:
            case 4:
            case 6:
            case 8:
            case 9:
                return op;
        }
    }

    return ERROR;
}

/* メニュー表示 */
void menu_print(void)
{
    printf("\n");
    printf("コマンドを入力してください\n");
    printf("---------------------------\n");
    printf("1 : ペンアップ\n");
    printf("2 : ペンダウン\n");
    printf("3 : 右に曲がる\n");
    printf("4 : 左に曲がる\n");
    printf("5,n : 前方にn歩進む\n");
    printf("6 : 配列を表示\n");
    printf("8 : ペン状態表示\n");
    printf("9 : 終了\n\n");
}

/* 配列表示 */
void print_array(int a[][ROW], int line, int row)
{
    int i, j;

    for (i = 0; i < line; i++)
    {
        for (j = 0; j < row; j++)
        {
            putchar(a[i][j] ? '*' : ' ');
        }

        putchar('\n');
    }
}

/* ペン移動 */
void pen_move(int p[][ROW], int line, int row,
              PEN *pen, int move)
{
    int dx[] = {0, 1, 0, -1};
    int dy[] = {-1, 0, 1, 0};

    int i;

    int nx = pen->x + dx[pen->direction] * move;
    int ny = pen->y + dy[pen->direction] * move;

    if (nx < 0 || nx >= row ||
        ny < 0 || ny >= line)
    {
        printf("進みきれません\n");
        return;
    }

    if (pen->state == PEN_DOWN)
    {
        for (i = 0; i <= move; i++)
        {
            p[
                pen->y + dy[pen->direction] * i
             ][
                pen->x + dx[pen->direction] * i
             ] = 1;
        }
    }

    pen->x = nx;
    pen->y = ny;
}

/* ペン状態表示 */
void print_pen_state(PEN *pen)
{
    const char *dir_name[] =
    {
        "NORTH",
        "EAST",
        "SOUTH",
        "WEST"
    };

    printf("\nペンの状態\n");
    printf("------------------\n");

    printf("方向 : %s\n",
           dir_name[pen->direction]);

    printf("座標 : (%d,%d)\n",
           pen->x - ROW / 2,
           -(pen->y - LINE / 2));

    printf("状態 : %s\n",
           pen->state == PEN_UP ?
           "PEN UP" : "PEN DOWN");
}
6.24: ナイトの巡回
  • b: 標準巡回
source
#include <stdio.h>
#include <conio.h>

#define ROW 8
#define COL 8

void init_board(int [][COL], int, int);

void print_board(int [][COL], int, int);

int move_check(int [][COL], int, int, int, int);

int main()
{
    int board[ROW][COL];

    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};

    int currentRow, currentCol;
    int moveNumber;
    int counter;
    int x, y;

    counter = 1;
    
    init_board(board, ROW, COL);
    print_board(board, ROW, COL);

    printf("初期位置を指定してください\n");
    scanf("%d", &currentRow);
    scanf("%d", &currentCol);
 
    board[currentRow][currentCol] = counter;
     
    while (counter <= 64)
    { 
         for (moveNumber = 0; moveNumber < 8; moveNumber++)
         {  
             y = currentRow + vertical[moveNumber];
             x = currentCol + horizontal[moveNumber];

             if ((0 <= y && y < ROW) && 
                 (0 <= x && x < COL) &&
                 (board[y][x] == 0 )     )
             { 
                 currentRow += vertical[moveNumber];
                 currentCol += horizontal[moveNumber];
                 board[currentRow][currentCol] = ++counter;
                 break;
             }
         }

         if (moveNumber == 8)
         {   
             printf("巡回不可能\n");
             printf("counter %d\n", counter);
             print_board(board, ROW, COL);
             return -1;
         }
    }
    printf("到達可能\n");
    print_board(board, ROW, COL);
  
    getch();
    return 0;
}

void init_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            b[i][j] = 0;
        }
    }
}

void print_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            printf("%3d ", b[i][j]);
        }
        printf("\n");
    }
}
  • c : 到達可能性に基づく発見的手法を活用
source
#include <stdio.h>
#include <string.h>

#define ROW 8
#define COL 8

void init_board(int b[ROW][COL]) {
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            b[i][j] = 0;
}

void print_board(int b[ROW][COL]) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++)
            printf("%3d ", b[i][j]);
        printf("\n");
    }
}

void initAccessibility(int accessibility[ROW][COL]) {
    int temp[ROW][COL] = {
        {2, 3, 4, 4, 4, 4, 3, 2},
        {3, 4, 6, 6, 6, 6, 4, 3},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {3, 4, 6, 6, 6, 6, 4, 3},
        {2, 3, 4, 4, 4, 4, 3, 2}
    };
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            accessibility[i][j] = temp[i][j];
}

void updateAccessibility(int accessibility[ROW][COL], int board[ROW][COL], int row, int col,
                         int vertical[], int horizontal[]) {
    for (int move = 0; move < 8; move++) {
        int ny = row + vertical[move];
        int nx = col + horizontal[move];
        if (ny >= 0 && ny < ROW && nx >= 0 && nx < COL && board[ny][nx] == 0)
            accessibility[ny][nx]--;
    }
}

int main() {
    int board[ROW][COL];
    int accessibility[ROW][COL];
    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int vertical[]   = {-1, -2, -2, -1, 1, 2, 2, 1};

    int clear = 0;
    char string[10000] = "";

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            init_board(board);
            initAccessibility(accessibility);

            int currentRow = i, currentCol = j;
            int counter = 1;
            board[currentRow][currentCol] = counter;
            updateAccessibility(accessibility, board, currentRow, currentCol, vertical, horizontal);

            while (counter < 64) {
                int min = 9999, found = 0;
                int min_x = -1, min_y = -1;

                for (int move = 0; move < 8; move++) {
                    int y = currentRow + vertical[move];
                    int x = currentCol + horizontal[move];
                    if (y >= 0 && y < ROW && x >= 0 && x < COL && board[y][x] == 0) {
                        found = 1;
                        if (accessibility[y][x] < min) {
                            min = accessibility[y][x];
                            min_x = x;
                            min_y = y;
                        }
                    }
                }

                if (!found) break;

                currentRow = min_y;
                currentCol = min_x;
                board[currentRow][currentCol] = ++counter;
                updateAccessibility(accessibility, board, currentRow, currentCol, vertical, horizontal);
            }

            if (counter == 64) {
                printf("complete: start at row %d col %d\n", i, j);
                print_board(board);
                clear++;
                char tmp[20];
                snprintf(tmp, sizeof(tmp), "row %d col %d\n", i, j);
                strcat(string, tmp);
            }
            else
            {
                printf("not complete: start at row %d col %d\n", i, j);
                print_board(board);
            }
        }
    }

    printf("complete patter num: %d\n%s", clear, string);
    return 0;
}
  • d : 2つ以上同点の升目があった場合、そこからさらに到達できる升目を調べて、どれか1つを選ぶように修正
source
#include <stdio.h>
#include <string.h>

#define ROW 8
#define COL 8

void init_board(int b[ROW][COL]) {
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            b[i][j] = 0;
}

void initAccessibility(int accessibility[ROW][COL]) {
    int temp[ROW][COL] = {
        {2, 3, 4, 4, 4, 4, 3, 2},
        {3, 4, 6, 6, 6, 6, 4, 3},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {3, 4, 6, 6, 6, 6, 4, 3},
        {2, 3, 4, 4, 4, 4, 3, 2}
    };
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            accessibility[i][j] = temp[i][j];
}

int min_access_from(int y, int x, int board[ROW][COL], int accessibility[ROW][COL],
                    int vertical[], int horizontal[]) {
    int min = 9999;
    for (int move = 0; move < 8; move++) {
        int ny = y + vertical[move];
        int nx = x + horizontal[move];
        if (ny >= 0 && ny < ROW && nx >= 0 && nx < COL && board[ny][nx] == 0) {
            if (accessibility[ny][nx] < min)
                min = accessibility[ny][nx];
        }
    }
    return min;
}

int main() {
    int board[ROW][COL];
    int accessibility[ROW][COL];
    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int vertical[]   = {-1, -2, -2, -1, 1, 2, 2, 1};

    int clear = 0;
    char string[10000] = "";

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            init_board(board);
            initAccessibility(accessibility);

            int currentRow = i, currentCol = j;
            int counter = 1;
            board[currentRow][currentCol] = counter;

            while (counter < 64) {
                int min_access = 9999;
                int found = 0;

                // 候補マスを一時保存
                int candidates_x[8], candidates_y[8], candidate_count = 0;

                for (int move = 0; move < 8; move++) {
                    int y = currentRow + vertical[move];
                    int x = currentCol + horizontal[move];
                    if (y >= 0 && y < ROW && x >= 0 && x < COL && board[y][x] == 0) {
                        int acc = accessibility[y][x];
                        if (acc < min_access) {
                            min_access = acc;
                            candidate_count = 0;
                            candidates_x[0] = x;
                            candidates_y[0] = y;
                            candidate_count++;
                            found = 1;
                        } else if (acc == min_access) {
                            candidates_x[candidate_count] = x;
                            candidates_y[candidate_count] = y;
                            candidate_count++;
                        }
                    }
                }

                if (!found) break;

                // 候補の中から最も「次のaccessibilityが小さい」ものを選ぶ
                int best_index = 0;
                int best_future = 9999;
                for (int k = 0; k < candidate_count; k++) {
                    int future = min_access_from(candidates_y[k], candidates_x[k], board, accessibility, vertical, horizontal);
                    if (future < best_future) {
                        best_future = future;
                        best_index = k;
                    }
                }

                currentRow = candidates_y[best_index];
                currentCol = candidates_x[best_index];
                board[currentRow][currentCol] = ++counter;

                // accessibility を更新
                for (int move = 0; move < 8; move++) {
                    int ny = currentRow + vertical[move];
                    int nx = currentCol + horizontal[move];
                    if (ny >= 0 && ny < ROW && nx >= 0 && nx < COL && board[ny][nx] == 0)
                        accessibility[ny][nx]--;
                }
            }

            if (counter == 64) {
                //printf("到達可能: row %d col %d\n", i, j);
                clear++;
                char tmp[20];
                snprintf(tmp, sizeof(tmp), "%d row %d col %d\n", clear, i, j);
                strcat(string, tmp);
            }
        }
    }

    printf("complete patter num: %d\n%s", clear, string);
    return 0;
}
6.25: ナイト巡回(腕力的手法)
  • a: 乱数生成を使ってナイトがチェス盤の上をランダムに動けるように、練習問題6.24 bのナイト巡回プログラムを改造
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

#define ROW 8
#define COL 8

#define MOVE 8

void init_board(int [][COL], int, int);

void print_board(int [][COL], int, int);

int check(int [], int, int);

int main()
{
    int board[ROW][COL];  // 升目
    int move[MOVE];       // 試された移動の番号を格納

    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};  // 移動タイプ
    int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};    // 

    int currentRow, currentCol;
    int moveNumber;
    int movefaile; // 移動に失敗した回数
    int counter;   // 移動回数
    int x, y;      

    counter = 1;
    movefaile = 0;
    
    srand(time(NULL));
    init_board(board, ROW, COL);
    print_board(board, ROW, COL);

    printf("初期位置を指定してください\n");
    scanf("%d", &currentRow);
    scanf("%d", &currentCol);
 
    board[currentRow][currentCol] = counter;
     
    while (counter < 64) // 全ての升目を訪れるまで
    { 
         do  // まだ試されていない移動パターンが選択されるまでループ
         {
            moveNumber = rand() % 8;
         }
         while (check(move,movefaile,moveNumber) == 1);
        
         y = currentRow + vertical[moveNumber];
         x = currentCol + horizontal[moveNumber];

         if ((0 <= y && y < ROW) &&   // 移動できるならば
             (0 <= x && x < COL) &&
             (board[y][x] == 0 )     )
         { 
              movefaile = 0;
              currentRow += vertical[moveNumber];
              currentCol += horizontal[moveNumber];
              board[currentRow][currentCol] = ++counter;
         }
         else                         // 移動できないならば
         {
              move[movefaile] = moveNumber;
              movefaile++;
         }

         if (movefaile == 8)          // どの方向にも移動できないならば
         {   
             printf("巡回不可能\n");
             printf("counter %d\n", counter);
             print_board(board, ROW, COL);
             return -1;
         }
    }
    printf("到達可能\n");
    print_board(board, ROW, COL);
  
    getch();
    return 0;
}

void init_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            b[i][j] = 0;
        }
    }
}

void print_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            printf("%3d ", b[i][j]);
        }
        printf("\n");
    }
}

int check(int m[], int now, int moveNum)
{
    int i;

    for (i = 0; i < now ; i++)
    {
       if (m[i] == moveNum)
       {
           return 1;
       }
    }
    return 0;
}
  • b : aのプログラムでは全般的に到達できる距離が以前に比べて短くなるため1000回巡回を行うよう変更
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define ROW 8
#define COL 8

#define MOVE 8

#define TRY 1000U
#define MAX 1000

void init_board(int [][COL], int, int);

void print_board(int [][COL], int, int);

int check(int [], int, int);

void print_info(int [], unsigned int);

void print_info_table(int *[], int, int);

int main()
{
    int board[ROW][COL];  // 升目
    int move[MOVE];       // 今まで試されたパターンで失敗したパターンを格納
    int info[TRY];
    int *p;
    int *info_table[MAX];

    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2}; // ナイトの移動パターン
    int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};  

    int currentRow, currentCol;
    int moveNumber;
    int movefaile; // 移動に失敗した回数
    int counter;   // 移動回数
    int x, y;    
    int now; 
    unsigned int i; 

    
    srand(time(NULL));
    init_board(board, ROW, COL); 

    
    now = 0;
    info_table[now] = info;
    p = info;

    for (i = 0; i < TRY; i++)
    {
       init_board(board, ROW, COL);
       counter = 1;   // 初期化
       movefaile = 0; 
       currentRow = rand() % ROW; 
       currentCol = rand() % COL;
       board[currentRow][currentCol] = counter;
 
       while (counter < 64)  
       { 
            do  // まだ試されていない移動パターンが選択されるまでループ
            {
               moveNumber = rand() % 8;
            }
            while (check(move,movefaile,moveNumber) == 1);
        
            y = currentRow + vertical[moveNumber];
            x = currentCol + horizontal[moveNumber];

            if ((0 <= y && y < ROW) &&   // 移動できるならば
                (0 <= x && x < COL) &&
                (board[y][x] == 0 )     )
            { 
                 movefaile = 0;
                 currentRow += vertical[moveNumber];
                 currentCol += horizontal[moveNumber];
                 board[currentRow][currentCol] = ++counter;
            }
            else // 移動できないならば
            {
                 move[movefaile] = moveNumber;
                 movefaile++;
            }

            if (movefaile == 8) // どの方向にも移動できないならば
            {   
                break;
            }
       }
       p[i] = counter;
    } 
    
    for (i = 0; i < TRY; i++)
    {
        printf("p[%d] %d\n", i, p[i]);
    }

    getch();
    
    return 0;
}

void init_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            b[i][j] = 0;
        }
    }
}

void print_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            printf("%3d ", b[i][j]);
        }
        printf("\n");
    }
}

int check(int m[], int now, int moveNum)
{
    int i;

    for (i = 0; i < now ; i++)
    {
       if (m[i] == moveNum)
       {
           return 1;
       }
    }
    return 0;
}

void print_info(int info[], unsigned int size)
{
    unsigned int i;
    int max = -1;

    for (i = 0; i < size; i++)
    {
       if (max < info[i])
       { 
           max = info[i];
       }
       printf("%9d %2d", i + 1, info[i]);
       
       if ((i + 1) % 6 == 0)
       {
           printf("\n");
       }
    }
    printf("もっとも進んだのは %d歩\n", max);
}

void print_info_table(int *t[], int size, int try)
{
    int i, j;
    int x;
    int *p;
   
    x = TRY;

    for (i = 0; i <= size; i++)
    {
        p = t[i];
        printf("%dセット目 \n", size + 1);

        if (i == size)
        {  
            x = try;
        }

        for (j = 0; j <= x; j++)
        {
            printf("%5d %2d", j + 1, p[j] );
        } 

        if ((j + 1) % 6 == 0)
        {
           printf("\n");
        }
    }
}
  • c : bのプログラムから繰り返しの制限を外して、完全な巡回が現れるまで実行されるよう変更
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

#define ROW 8
#define COL 8
#define MOVE 8

void init_board(int [][COL], int, int);
void print_board(int [][COL], int, int);
int check(int [], int, int);

int main(void)
{
    int board[ROW][COL];
    int move[MOVE];
    int freq[65] = {0};      /* 巡回長ごとの回数 */

    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int vertical[]   = {-1, -2, -2, -1, 1, 2, 2, 1};

    int currentRow, currentCol;
    int moveNumber;
    int movefaile;
    int counter;
    int x, y;
    int i;

    unsigned long long trial = 0;

    srand((unsigned)time(NULL));

    while (1)
    {
        trial++;

        init_board(board, ROW, COL);

        counter = 1;
        movefaile = 0;

        currentRow = rand() % ROW;
        currentCol = rand() % COL;
        board[currentRow][currentCol] = counter;

        while (counter < 64)
        {
            do
            {
                moveNumber = rand() % 8;
            }
            while (check(move, movefaile, moveNumber));

            y = currentRow + vertical[moveNumber];
            x = currentCol + horizontal[moveNumber];

            if ((0 <= y && y < ROW) &&
                (0 <= x && x < COL) &&
                (board[y][x] == 0))
            {
                movefaile = 0;
                currentRow = y;
                currentCol = x;
                board[currentRow][currentCol] = ++counter;
            }
            else
            {
                move[movefaile] = moveNumber;
                movefaile++;

                if (movefaile == 8)
                    break;
            }
        }

        /* 巡回長を記録 */
        freq[counter]++;

        /* 完全巡回なら終了 */
        if (counter == 64)
        {
            printf("完全な巡回を発見しました！\n");
            printf("試行回数 : %llu\n\n", trial);

            print_board(board, ROW, COL);

            printf("\n巡回長   回数\n");
            printf("-----------------\n");

            for (i = 1; i <= 64; i++)
            {
                if (freq[i] != 0)
                {
                    printf("%3d %10d\n", i, freq[i]);
                }
            }

            break;
        }
    }

    getch();
    return 0;
}

void init_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            b[i][j] = 0;
        }
    }
}

void print_board(int b[][COL], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            printf("%3d ", b[i][j]);
        }
        printf("\n");
    }
}

int check(int m[], int now, int moveNum)
{
    int i;

    for (i = 0; i < now; i++)
    {
        if (m[i] == moveNum)
        {
            return 1;
        }
    }

    return 0;
}
6.26:8クイーン
source
#include <stdio.h>

#define SIZE 8

int board[SIZE][SIZE] = {0};
int access[SIZE][SIZE] = {
    {22,22,22,22,22,22,22,22},
    {22,24,24,24,24,24,24,22},
    {22,24,26,26,26,26,24,22},
    {22,24,26,28,28,26,24,22},
    {22,24,26,28,28,26,24,22},
    {22,24,26,26,26,26,24,22},
    {22,24,24,24,24,24,24,22},
    {22,22,22,22,22,22,22,22}
};

void print_board() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%3d", board[i][j]);
        }
        printf("\n");
    }
}

void mark_attacks(int row, int col, int queen_num) {
    for (int i = 0; i < SIZE; i++) {
        board[row][i] = queen_num;
        board[i][col] = queen_num;
    }

    for (int i = -SIZE; i < SIZE; i++) {
        int r1 = row + i, c1 = col + i;
        int r2 = row + i, c2 = col - i;
        if (r1 >= 0 && r1 < SIZE && c1 >= 0 && c1 < SIZE) board[r1][c1] = queen_num;
        if (r2 >= 0 && r2 < SIZE && c2 >= 0 && c2 < SIZE) board[r2][c2] = queen_num;
    }

    board[row][col] = queen_num + 10; // The actual location
}

void update_access() {
    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            if (board[r][c] == 0) {
                int count = 0;
                for (int i = 0; i < SIZE; i++) {
                    if (board[r][i] == 0) count++;  
                    if (board[i][c] == 0) count++; 
                }

                for (int i = -SIZE; i < SIZE; i++) {
                    int r1 = r + i, c1 = c + i;
                    int r2 = r + i, c2 = c - i;
                    if (r1 >= 0 && r1 < SIZE && c1 >= 0 && c1 < SIZE && board[r1][c1] == 0) count++;
                    if (r2 >= 0 && r2 < SIZE && c2 >= 0 && c2 < SIZE && board[r2][c2] == 0) count++;
                }

                // (r,c) is duplicate-count in four directions, so reduce it by three times.
                count -= 3;

                access[r][c] = count;
            } else {
                access[r][c] = -1;
            }
        }
    }
}

int main() {
    int queen = 1;

    while (queen <= SIZE) {
        int min = 1000, x = -1, y = -1;
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (access[r][c] >= 0 && access[r][c] < min && board[r][c] == 0) {
                    min = access[r][c];
                    y = r;
                    x = c;
                }
            }
        }

        if (x == -1 || y == -1) {
            printf("I couldn't place all the queens. I could put up to %d\n", queen - 1);
            break;
        }

        mark_attacks(y, x, queen);
        update_access();
        queen++;
    }

    print_board();
    return 0;
}
6.27:8クイーン(腕力的手法)
  • a: 6.25で開発した乱数生成による腕力的手法を活用
source
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>

#define DEBUG(x) 

#define ROW 8
#define COL 8

void init_ban(int [][COL]);
int check(int [][COL], int, int, int);
void printBan(int [][COL]);
int checkPutOn(int [][COL]);


int main()
{               
    int nowRow, nowCol; 
    int ban[ROW][COL]; 
    int queen; 
    int put;            // whether queen can be placed 
    int i;

    srand(time(NULL));
    for(i = 0; i < 100000; i++)
    {
        init_ban(ban);
        queen = 1;
 
        nowRow = rand() % ROW;
        nowCol = rand() % COL;

        // Update the board by placing the first queen
        check(ban, nowRow, nowCol, queen); 
        DEBUG(printBan(ban);printf("\n");getch();)
        put = 1;
        queen++; 
        printf("%d ", i);
        // Place all 8 queens without attacking each other.
        while (put == 1 && queen <= 8)
        {   
            // The queen hasn't been placed yet.
            put = 0;
    
            // Loop until you find a place to put the queen
            while (1)
            {
                nowRow = rand() % ROW;
                nowCol = rand() % COL;

                // Can't be in that place
                if (ban[nowRow][nowCol] != 0)
                {
                    // If there's no more room on the board
                    if (checkPutOn(ban) == 0)
                    {
                        printf("Only %d items could be placed\n", queen - 1);
                        break;
                    }
                }
                // Can be in that place
                else
                {
                    check(ban, nowRow, nowCol, queen);
                    DEBUG(printBan(ban);printf("\n");getch();)
                    queen++;

                    put = 1;
                    break; // go to A
                }
            }
            // A
        }
        // I was able to place all the queens.
        if (queen >= 9)
        {
            printf("success\n");
            printBan(ban);
            printf("\n");
        }    
    }
    getch();
    return 0;
}

void init_ban(int b[][COL])
{
    int i, j;

    for (i = 0; i < ROW; i++)
    {
       for (j = 0; j < COL; j++)
       {
          b[i][j] = 0;
       }
    }
}

int check(int b[][COL], int y, int x, int phase)
{
    int i, j; 
    int count = 0;
     
    // 横方向を埋める 
    for (i = 0;i < COL; i++)
    {
        b[y][i] = phase;
        count++;
    }
 
    count--;
    // 縦方向を埋める
    for (i = 0; i < ROW; i++)
    {
        b[i][x] = phase;
        count++;
    }
   
    j = x - 1;
    i = y - 1;
    // 左斜め上方向を埋める
    while (0 <= i && 0 <= j)
    {
         b[i][j] = phase;
         i--;
         j--;
         count++;
    }

    j = x - 1;
    i = y + 1;
    // 左斜め下方向を埋める
    while (0 <= j  && i < ROW)
    {
         b[i][j] = phase;
         i++;
         j--;
         count++;
    }

    j = x + 1;
    i = y + 1;
    // 右斜め下方向を埋める
    while (j < COL && i < ROW)
    {
         b[i][j] = phase;
         i++;
         j++;
         count++;
    }

    j = x + 1;
    i = y - 1;
    // 右斜め上方向を埋める
    while (j < ROW && 0 <= i)
    {
         b[i][j] = phase;
         i--;
         j++;
         count++;
    }
    b[y][x] = phase + 10;

    return count;

}

void printBan(int b[][COL])
{
    int i, j;

    for (i = 0; i < ROW; i++)
    {
       for (j = 0; j < COL; j++)
       {
            printf("%3d", b[i][j]);        
       }
       printf("\n");
    }
}

// まだ置ける場所があるかを調べる
// 戻り値 1 まだ置く場所がある 0 もう置く場所がない
int checkPutOn(int b[][COL])
{
   int i, j;

   for (i = 0; i < ROW; i++)
   {
      for (j = 0; j < COL; j++)
      {
         // 置ける場所がある
         if (b[i][j] == 0)
         {
             return 1;
         }
      }
   }
   // 置ける場所がない
   return 0;
}
  • b:しらみつぶし法
source
#include <stdio.h>
#define SIZE 8

int board[SIZE]; // board[i] = j は i行目のj列にクイーンがあることを意味する

int is_safe(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col ||                      // 同じ列
            board[i] - i == col - row ||            // 右上↙左下の斜め
            board[i] + i == col + row)              // 左上↘右下の斜め
            return 0;
    }
    return 1;
}

void print_board() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (board[i] == j)
                printf(" Q ");
            else
                printf(" . ");
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    int row = 0;
    int col[SIZE] = {0}; // 各行で次に試す列番号
    int solutions = 0;

    while (row >= 0) {
        if (col[row] >= SIZE) {
            // すべての列を試した → 戻る
            col[row] = 0;
            row--;
            if (row >= 0) col[row]++;
        } else if (is_safe(row, col[row])) {
            board[row] = col[row];
            row++;
        } else {
            col[row]++;
        }

        if (row == SIZE) {
            // 解が見つかった
            print_board();
            solutions++;
            row--;
            col[row]++;
        }
    }

    printf("解の総数: %d\n", solutions);
    return 0;
}
6.28:1から20までの乱数を20個生成し、重複しない値だけを配列に格納
source
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 20

// 配列の中にその値が既にあるかをチェック
int checkValue(int [], int, int);

// 配列のデータを表示
void printArray(int [], int);


int main()
{
    int data[SIZE];
    int i;
    int now = 0; // 次にデータを格納する配列のインデックス
    int value;   // 乱数値を格納

    // 20回乱数を生成
    for (i = 1; i <= 20; i++)
    {
       // 1-20までの値を生成
       value = rand() % 20 + 1;
       printf("%d\n", value);
 
       // 配列にその値がまだない
       if (checkValue(data, now, value) == -1)
       {
           // データ挿入
           data[now] = value;
           now++;
       }
    }

    // 結果表示
    printArray(data, now);
    getch();
    return 0;
}

// 配列の中にその値が既にあるかをチェック
// 戻り値 -1以外 その値がある配列のインデックス 
//        -1     その値は存在しない
int checkValue(int array[], int size, int value)
{
   int i;

   for (i = 0; i < size; i++)
   {
      // 値がある
      if (array[i] == value)
      {
          return i;
      }
   }

   // 値がない
   return -1;
}

// 配列のデータを表示
void printArray(int array[], int size)
{
   int i;

   for (i = 0; i < size; i++)
   {
      printf("%3d %3d  ", i, array[i]);

      if ((i + 1) % 3 == 0)
      {
          printf("\n");
      }
   }
}
6.29:6.24で書いたナイト巡回プログラムを変更して、完全な巡回が達成されたとき、それが閉じた巡回であるかを検査
source
// customize 6.24c.c

#include <stdio.h>
#include <string.h>

#define ROW 8
#define COL 8

void init_board(int b[ROW][COL]) {
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            b[i][j] = 0;
}

void print_board(int b[ROW][COL]) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++)
            printf("%3d ", b[i][j]);
        printf("\n");
    }
}

void initAccessibility(int accessibility[ROW][COL]) {
    int temp[ROW][COL] = {
        {2, 3, 4, 4, 4, 4, 3, 2},
        {3, 4, 6, 6, 6, 6, 4, 3},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {4, 6, 8, 8, 8, 8, 6, 4},
        {3, 4, 6, 6, 6, 6, 4, 3},
        {2, 3, 4, 4, 4, 4, 3, 2}
    };
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            accessibility[i][j] = temp[i][j];
}

void updateAccessibility(int accessibility[ROW][COL], int board[ROW][COL], int row, int col,
                         int vertical[], int horizontal[]) {
    for (int move = 0; move < 8; move++) {
        int ny = row + vertical[move];
        int nx = col + horizontal[move];
        if (ny >= 0 && ny < ROW && nx >= 0 && nx < COL && board[ny][nx] == 0)
            accessibility[ny][nx]--;
    }
}

int main() {
    int board[ROW][COL];
    int accessibility[ROW][COL];
    int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int vertical[]   = {-1, -2, -2, -1, 1, 2, 2, 1};

    int clear = 0;
    char string[10000] = "";

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            init_board(board);
            initAccessibility(accessibility);

            int currentRow = i, currentCol = j;
            int counter = 1;
            board[currentRow][currentCol] = counter;
            updateAccessibility(accessibility, board, currentRow, currentCol, vertical, horizontal);

            while (counter < 64) {
                int min = 9999, found = 0;
                int min_x = -1, min_y = -1;

                for (int move = 0; move < 8; move++) {
                    int y = currentRow + vertical[move];
                    int x = currentCol + horizontal[move];
                    if (y >= 0 && y < ROW && x >= 0 && x < COL && board[y][x] == 0) {
                        found = 1;
                        if (accessibility[y][x] < min) {
                            min = accessibility[y][x];
                            min_x = x;
                            min_y = y;
                        }
                    }
                }

                if (!found) break;

                currentRow = min_y;
                currentCol = min_x;
                board[currentRow][currentCol] = ++counter;
                updateAccessibility(accessibility, board, currentRow, currentCol, vertical, horizontal);
            }

            if (counter == 64) {

                for(int move = 0; move < 8; move++)
                {
                    int y = currentRow + vertical[move];
                    int x = currentCol + horizontal[move];
                    if (y >= 0 && y < ROW && x >= 0 && x < COL && board[y][x] == 1) 
                    {
                        printf("Closed patrol\n");
                    }
                }
                printf("complete: start at row %d col %d\n", i, j);
                print_board(board);
                clear++;
                char tmp[20];
                snprintf(tmp, sizeof(tmp), "row %d col %d\n", i, j);
                strcat(string, tmp);
            }
            else
            {
                printf("not complete: start at row %d col %d\n", i, j);
                print_board(board);
            }
        }
    }

    printf("complete patter num: %d\n%s", clear, string);
    return 0;
}
6.30:エラトステネスのふるい
source
#include <stdio.h>
#include <conio.h>

#define SIZE 1001

// 配列をある値で初期化
void initArray(int [], int, int);

int main()
{
    int num[SIZE];
    int i, j;
    int tmp;

    // 全ての要素を1で初期化する
    initArray(num, SIZE, 1);

    // 2-999まで探索
    for (i = 2; i < SIZE - 1; i++)
    {
       // 配列の要素が1ならば
       if (num[i] == 1)
       {
           // それ以降の倍数を全てチェックする
           for (j = 2; (i * j) < SIZE - 1; j++)
           {
              tmp = i * j;
              num[tmp] = 0;
           }
       }
    }

    // 1-999までの素数を表示
    for (i = 1; i < SIZE - 1; i++)
    {
       if (num[i] == 1)
       {
           printf("%3dは素数\n", i);
       }
    }
    getch();
    return 0;
}

// 配列をある値で初期化
void initArray(int array[], int size, int value)
{
   int i;

   for (i = 0; i < size; i++)
   {
      array[i] = value;
   }
}
6.31:バケツソート
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#define SIZE 3

void init(int [][SIZE], int, int);

void printBaketu(int [][SIZE], int, int);

int getMax(int [], int);

void bucketSort(int [], int);

int main()
{
    int i;
    int data[SIZE]  = {97, 3, 100};
  
    bucketSort(data, SIZE);

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

void printBaketu(int d[][SIZE], int row, int col)
{
    int i, j;


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

int getMax(int d[], int size)
{
    int i = 0;
    int max;

    max = d[i];
    i++;

    while (i < size)
    {
       if (max < d[i])
       {
           max = d[i];
       }
       i++;
    }
    return max;
}

void init(int d[][SIZE], int row, int col)
{
    int i, j;

    for (i = 0; i < row; i++)
    {
       for (j = 0; j < col; j++)
       {
          d[i][j] = 0;
       }
    }
}

void bucketSort(int data[], int size)
{
    static int rowNext[10];
    int baketu[10][SIZE];
    int selectRow;
    int next = 0;                   // 次に1次元配列のどの部分にデータを格納するか
    int max;
    int count;
    int num = 1;
    int i, j;

    max = getMax(data, SIZE);

    while (max / 10 > 0)
    {
         max /= 10;
         num++;
    }
 
    for (count = 1; count <= num; count++)
    {
       init(baketu, 10, size);
       // 第1パス
       for (i = 0; i < size; i++)
       {
           selectRow = (data[i] / (int)pow(10, count - 1)) % 10;
           baketu[selectRow][rowNext[selectRow]] = data[i];
           rowNext[selectRow]++;
       }

       // 第2パス
       for (i = 0; i < 10; i++)
       {
           for (j = 0; j < rowNext[i]; j++)
           { 
               // バケツから配列へ
               data[next] = baketu[i][j];
               next++;
           }
           // バケツのデータはないので0に初期化
           rowNext[i] = 0;
       } 
       next = 0;
    }
}
6.32:選択ソート(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

void selectionSort(int [], int);

int main()
{
    int i;
    int data[4] = {5, 4, 8, 2};


    printf("ソート前\n");    
    for (i = 0; i < 4; i++)
    {
       printf("%d\n", data[i]);

    }

    selectionSort(data, 4);
    
    printf("ソート後\n");
    for (i = 0; i < 4; i++)
    {
       printf("%d\n", data[i]);

    }
    getch();
    return 0;
}

void selectionSort(int d[], int size)
{
    int min = 0;
    int i = 1;
    int tmp;

    if (size == 1)
    {
        return;
    }

    while (i < size)
    {
        if (d[min] > d[i])
        {
            min = i;
        }
        i++;
    }
    
    tmp = d[min];
    d[min] = d[0];
    d[0] = tmp;

    selectionSort(d + 1, size - 1);
}
6.33: 回文判定(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

int testPalindrome(char [], int, int);

int main()
{
    char string[100];

    printf("文字列を入力してください\n");
    gets(string);

    printf("%d",testPalindrome(string, 0, strlen(string) - 1));
    getch();
    return 0;
}

int testPalindrome(char s[], int left, int right)
{
    if (left >= right)
    {
        return 1;
    }
   
    while (s[left]  == ',') left++;
    
    while (s[right] == ',') right--;

    if (s[left] == s[right])
    {
        return testPalindrome(s, left + 1, right - 1);
    }
    else
    {
        return 0;
    }
}
6.34:線形サーチ(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

int linearSearch(int [], int, int);

int main()
{
    int data[3] = {2, 3, 4};

    printf("%d\n", linearSearch(data, 0, 3));
    getch();
    return 0;
}

int linearSearch(int array[], int key, int size)
{ 
    int static count;

    if (array[0] == key)
    {
        return count;
    }
    else
    {
        if (size == 1)
        { 
            return -1;
        }
        count++;
        return linearSearch(array + 1, key, size - 1);
    }
}
6.35:二分サーチ(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

#define SIZE 15

int binarySearch(int [], int, int, int);

int main()
{
    int a[SIZE], key, result;
    int i;


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

    printf("0-28までの数字を入力してください"); 
    scanf("%d", &key);

    result = binarySearch(a, 0, SIZE - 1, key);
    printf("%d\n", result);
    getch();
    return 0;
}

int binarySearch(int d[], int low, int high, int key)
{
    int middle;

    if (low == high)
    {
        return -1;
    }
    middle = (low + high) / 2;
    

    if (d[middle] == key)
    {
        return middle;
    }
    else if (key < d[middle])
    {
        return binarySearch(d, low, middle - 1, key);
    }
    else 
    {
        return binarySearch(d, middle + 1, high, key);
    }
}
6.36:8クイーン(再帰)
source
#include <stdio.h>

#define SIZE 8

int board[SIZE][SIZE] = {0};
int access[SIZE][SIZE] = {
    {22,22,22,22,22,22,22,22},
    {22,24,24,24,24,24,24,22},
    {22,24,26,26,26,26,24,22},
    {22,24,26,28,28,26,24,22},
    {22,24,26,28,28,26,24,22},
    {22,24,26,26,26,26,24,22},
    {22,24,24,24,24,24,24,22},
    {22,22,22,22,22,22,22,22}
};

void print_board() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%3d", board[i][j]);
        }
        printf("\n");
    }
}

void mark_attacks(int row, int col, int queen_num) {
    for (int i = 0; i < SIZE; i++) {
        board[row][i] = queen_num;
        board[i][col] = queen_num;
    }

    for (int i = -SIZE; i < SIZE; i++) {
        int r1 = row + i, c1 = col + i;
        int r2 = row + i, c2 = col - i;
        if (r1 >= 0 && r1 < SIZE && c1 >= 0 && c1 < SIZE) board[r1][c1] = queen_num;
        if (r2 >= 0 && r2 < SIZE && c2 >= 0 && c2 < SIZE) board[r2][c2] = queen_num;
    }

    board[row][col] = queen_num + 10;
}

void update_access() {
    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            if (board[r][c] == 0) {
                int count = 0;
                for (int i = 0; i < SIZE; i++) {
                    if (board[r][i] == 0) count++;
                    if (board[i][c] == 0) count++;
                }

                for (int i = -SIZE; i < SIZE; i++) {
                    int r1 = r + i, c1 = c + i;
                    int r2 = r + i, c2 = c - i;
                    if (r1 >= 0 && r1 < SIZE && c1 >= 0 && c1 < SIZE && board[r1][c1] == 0) count++;
                    if (r2 >= 0 && r2 < SIZE && c2 >= 0 && c2 < SIZE && board[r2][c2] == 0) count++;
                }

                count -= 3;
                access[r][c] = count;
            } else {
                access[r][c] = -1;
            }
        }
    }
}

int place_queen(int queen_num) {
    if (queen_num > SIZE) {
        printf("All queens was placed！\n");
        return 1;
    }

    int min = 1000, x = -1, y = -1;

    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            if (access[r][c] >= 0 && access[r][c] < min && board[r][c] == 0) {
                min = access[r][c];
                y = r;
                x = c;
            }
        }
    }

    if (x == -1 || y == -1) {
        printf("can't all queens. Place up to %d pieces。\n", queen_num - 1);
        return 0;
    }

    mark_attacks(y, x, queen_num);
    update_access();
    return place_queen(queen_num + 1);
}

int main() {
    place_queen(1);
    print_board();
    return 0;
}
6.37:配列のプリント(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

void stringReverse(const char []);
void printArray(const char [], int);

int main()
{
    printArray("ABCD", strlen("ABCD"));
    getch();
    return 0;
}

void stringReverse(const char d[])
{
    if (d[0] == '\0')
    {
        return;
    }
    else
    {
        stringReverse(d + 1);
        printf("%c", d[0]); 
        return;
    }
}

void printArray(const char d[], int size)
{
    if (size == 0)
    {
        return;
    }
    else
    {
        printf("%c", d[0]);
        printArray(d + 1, size - 1);
        return;
    }
}
6.38:文字列の逆向きプリント(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

void stringReverse(const char []);
void printArray(const char [], int);

int main()
{
    stringReverse("ABCDEF");
    getch();
    return 0;
}

void stringReverse(const char d[])
{
    if (d[0] == '\0')
    {
        return;
    }
    else
    {
        stringReverse(d + 1);
        printf("%c", d[0]); 
        return;
    }
}

void printArray(const char d[], int size)
{
    if (size == 0)
    {
        return;
    }
    else
    {
        printf("%c", d[0]);
        printArray(d + 1, size - 1);
        return;
    }
}
6.39:配列の中の最小値を見つける(再帰)
source
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
#include <string.h>
#include <ctype.h>

int recursiveMinimum(int [], int);

int main()
{
   int data[4] = {3, 6, 6, 9};
 
   printf("最小値は %d\n", recursiveMinimum(data, 4));
   getch();
   return 0;
}

int recursiveMinimum(int a[], int size)
{
   int tmp;

   if (size == 1)
   {
       return a[0];
   }

   if (a[0] < a[1])
   {
       tmp = a[1];
       a[1] = a[0];
       a[0] = tmp;
   }

   return recursiveMinimum(a + 1, size - 1);
}
ポータルサイト
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?