C語言通過二分查詢實現猜數位遊戲

2023-02-05 14:01:58

二分查詢

題目：在一個有序陣列中查詢具體的某個數位n。

首先我們先定義一個1···10的陣列，如果7為我們要查詢的數位，編寫程式碼如下

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    //  下標          0 1 2 3 4 5 6 7 8 9
    int k = 7;//k是要查詢的數位
    int i = 0;
    int sz = sizeof(arr) / sizeof(arr[0]);
     //sz為陣列元素個數
    int flag = 0;//
    for (i = 0; i < sz; i++)
    {
        if (k == arr[i])
        {
            flag = 1;
            printf("找到了，下標是:%dn", i);
            break;
        }
    }
    if (flag == 0)
        printf("找不到n");

    return 0;
}

但是這個程式碼的效率比較低，需要回圈多次，所以我們需要用一個效率較高的方法：二分查詢又叫（折半查詢）

二分查詢的思想

給你一個有序的序列，取中間元素和目標元素進行對比，取其中的一半，丟棄另一半，快速縮小目標元素所在的位置。主要思想還是：快速縮小目標元素所在的區間。

二分查詢的條件

1.序列必須是有序的，升序或者降序都可以

2. 序列必須是順序儲存元素的，順序儲存元素主要是可以快速的獲取中間元素（可以通過下標來找到元素）

二分查詢的實現過程

分析：假設我們要找的數位為7，在查詢過程中要用下標進行查詢，此時我們定義左下標為left，右下標為right，中間元素下標為mid，（left+right）/2=mid。當第一次查詢沒有找到時，從中間下標向左或向右縮短查詢範圍繼續查詢，直到找到為止。

以數位7為例：第一次查詢（left+right）/2=（0+9）/2=4，下標為4找到的數位為5，此時並沒有找到；第二次查詢，因為數位5小於數位7，所以mid+1=left，right不變，向右查詢，此時（left+right）/2=（5+9）/2=7，下標為7，找到的數位為8，並沒有找到；第三次查詢，因為數位8大於數位7，所以mid-1=right，左下標不變，向左查詢，此時（left+right）/2=（5+6）/2=5，下標為5，找到的數位為6，第四次查詢，因為6小於7，所以向右查詢，（left+right）/2=（6+6）/2=6，下標為6，找到的數位為7。

程式碼舉例

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	// 下標       0 1 2 3 4 5 6 7 8 9
	int k = 7;//k是要查詢的數位
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	//折半查詢（二分查詢），前提是陣列有序
	int left = 0;
	int right = sz - 1;

	int flag = 0;
	while (left<=right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下標是：%dn", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到n");

	return 0;
}

如果left是一個很大的數，right也是一個很大的數，left+right超出整形能表達的最大值，資料溢位，此時（left+right）/2所求的就不是最大值了這時要怎麼辦呢？

我們讓多出的部分除以二在平分，如圖所示

程式碼修改

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	//            0 1 2 3 4 5 6 7 8 9
	int k = 7;//k是要查詢的數位
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	//折半查詢（二分查詢），前提是陣列有序
	int left = 0;
	int right = sz - 1;

	int flag = 0;
	while (left<=right)
	{
		int mid = left + (right - left) / 2;

		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下標是：%dn", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到n");

	return 0;
}

猜數位遊戲

遊戲說明

1.電腦生成一個1~100的的亂數

2.猜數位

猜大了就告訴你：猜大了

猜小了就告訴你：猜小了

猜對了就告訴你：恭喜你，猜對了

猜數位遊戲思想

首先要列印一個選單，選擇開始遊戲還是退出遊戲

其次，遊戲應該可以玩完一局之後玩一局，為迴圈進行，利用迴圈語句構建框架

程式碼實現

列印選單

void menu()
{
    printf("*****************************n");
    printf("*********   1. play  ********n");
    printf("*********   0. exit  ********n");
    printf("*****************************n");
}

列印結果

列印主函數

int main()
{
    int input = 0;
    do
    {
        menu();
        printf("請選擇:>");
        scanf("%d", &input);
        switch (input)
        {
        case 1:
            printf("猜數位n");
            break;
        case 0:
            printf("退出遊戲n");
            break;
        default:
            printf("選擇錯誤n");
            break;
        }
    } while (input);
    return 0;
}

此時遊戲過於簡單，選擇1要開始遊戲，所以我們定義一個遊戲函數game（）

列印遊戲函數

遊戲第一步：生成亂數

rand（）函數為生成亂數函數，標頭檔案為<stdlib.h>

rand會返回一個0~327637之間的數

使用rand（）要搭配srand（）一起使用，srand（）是設定亂數生成器，一般用時間戳作為時間的種子，所以使用time函數來獲取時間，然後將time函數轉換為（unsigned)型別在傳給srand函數

void game()
{
    //1. 生成亂數
    int ret = rand() % 100 + 1;//0~99+1-->1~100
    //2. 猜數位
    int guess = 0;
    while (1)
    {
        printf("請猜數位:>");
        scanf("%d", &guess);
        if (guess < ret)
        {
            printf("猜小了n");
        }
        else if (guess > ret)
        {
            printf("猜大了n");
        }
        else
        {
            printf("恭喜你，猜對了n");
            break;
        }
    }
}

整體程式碼演示

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void menu()
{
	printf("*****************************n");
	printf("*********   1. play  *******n");
	printf("*********   0. exit  ********n");
	printf("*****************************n");
}
//
//rand函數會返回一個0~32767之間的亂數
//
//時間戳

void game()
{
	//1. 生成亂數
	int ret = rand() % 100 + 1;//0~99+1-->1~100
	//2. 猜數位
	int guess = 0;
	while (1)
	{
		printf("請猜數位:>");
		scanf("%d", &guess);
		if (guess < ret)
		{
			printf("猜小了n");
		}
		else if (guess > ret)
		{
			printf("猜大了n");
		}
		else
		{
			printf("恭喜你，猜對了n");
			break;
		}
	}
}

int main()
{
	int input = 0;
	//設定了亂數的生成器
	srand((unsigned int)time(NULL));
    //給srand傳一個時間戳，是生成的數位足夠隨機
	do
	{
		menu();
		printf("請選擇:>");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			game();
			break;
		case 0:
			printf("退出遊戲n");
			break;
		default:
			printf("選擇錯誤n");
			break;
		}
	} while (input);
	return 0;
}

遊戲效果演示