天天看點
傳回

學堂線上-程式設計基礎-第四章第四章-篩法與查找

文章目錄

  • 第四章-篩法與查找
    • 4.1 插花遊戲
      • 筆記
      • 代碼實作
    • 4.2 篩法
      • 筆記
      • 4.2.3 代碼實作
      • 4.2.5 代碼實作
      • 4.2.7 代碼實作
      • 4.2.7 韓信點兵問題的數學了解
    • 4.3 線性查找
      • 筆記
      • 4.3.2 代碼實作
      • 4.3.4 代碼實作
    • 4.4 折半查找
      • 筆記
      • 代碼實作
    • 4.5 排序問題
      • 筆記
      • 4.5.1 代碼實作
      • 4.5.1 代碼簡化
      • 4.5.2 代碼實作
      • 4.5.3 代碼實作
      • 4.5.3 代碼拓展
      • 4.5.4 代碼實作
    • 文法自測-試題答案

第四章-篩法與查找

4.1 插花遊戲

筆記

  函數（function）是一個具有特定的功能的、相對獨立的子產品，能夠被多次使用。

  函數設計的要素：

功能：函數的定義（definition）
	子產品：函數的聲明（declaration）-->函數名，輸入類型，輸出類型
	使用：函數的調用（call）

  

代碼實作 

#include <iostream>
using namespace std;

bool isPrime(int);

int main() 
{
	for (int n = 2; n <= 100; n++)
		if (isPrime(n))
			cout << n <<endl;
	return 0; 
}

bool isPrime(int n)
{
	for (int i = 2; i*i <= n; i++)
		if (n % i == 0)
			return false;
	return true;
}

4.2 篩法

筆記

  數組定義：數組的類型，數組的名稱，變量的個數；

  篩法思路：埃拉托斯特尼篩法

初始化“篩子”-->枚舉-->用篩子篩選

4.2.3 代碼實作 

#include <iostream>
using namespace std;

const int N=100;
bool seive[N+1];

int main() 
{
	for (int i = 2; i <= N; i++)
		seive[i] = true;
	for (int d = 2; d*d <= N; d++)
		if (seive[d])
			for (int n = d*d; n <= N; n +=d)
				seive[n] = false;
	for (int n =2; n <= N; n++)
		if (seive[n])
			cout << n <<endl;
	return 0; 
}

4.2.5 代碼實作 

#include <iostream>
using namespace std;

int main() 
{
	int r3 = 0, r5 = 0, r7 = 0;
	int seive[200];
	cin >> r3 >> r5 >> r7;
	for (int i = 0; i < 200; i++)
		seive[i] = 0;
	for (int i = r3; i < 200; i = i + 3)
		seive[i]++;
	for (int i = r5; i < 200; i = i + 5)
		seive[i]++;
	for (int i = r7; i < 200; i = i + 7)
		seive[i]++;
	for (int i = 0; i < 200; i++)
		if (seive[i] == 3)
			cout << i <<endl;
	return 0; 
}

注意：循環中的 i 需要 小于 數組中變量個數，因為200個變量的數組最後一個位seive[199]

4.2.7 代碼實作 

#include <iostream>
using namespace std;

int main() 
{
	int r3 = 0, r5 = 0, r7 = 0;
	cin >> r3 >> r5 >> r7;
	int res =  (r3 * 70 + r5 * 21 + r7 * 15) % 105;
	cout << res <<endl;
	return 0; 
}

4.2.7 韓信點兵問題的數學了解

  • 能被 5,7 除盡數是 35k,其中 k=2，即70除3正好餘1，70a 除3正好餘a。
  • 能被 3,7 除盡數是 21k,其中 k=1，即21除5正好餘1，21b 除5正好餘b。
  • 能被 3,5 除盡數是 15k,其中 k=1，即15除7正好餘1，15c 除7正好餘c。

是以

  • 70a + 21b + 15c 除3正好餘a。
  • 70a + 21b + 15c 除5正好餘b。
  • 70a + 21b + 15c 除7正好餘c。

是以

（70a + 21b + 15c）%（3 * 5 * 7）為最小值

以上内容摘自網絡

4.3 線性查找

筆記

  線性查找：撲克牌問題

初始化-->枚舉-->判定查找-->找到跳出-->輸出

  查找最小值/最大值：

初始化-->枚舉-->判定查找-->更新判定值-->輸出

4.3.2 代碼實作 

#include <iostream>
using namespace std;

int main() 
{
	int cards[13] = {101,112,109,107,202,209,
					 213,212,313,303,403,412,402};
	int pos = -1;
	for (int i =0; i < 13; i++)
		if (cards[i] == 112)
		{
			pos = i;
			break;
		}
	if (pos != -1)
		cout << "黑桃Q是第" << pos + 1 << "張牌" <<endl;
	else 
		cout << "沒找到" <<endl; 
	return 0; 
}

4.3.4 代碼實作 

#include <iostream>
using namespace std;

int main() 
{
	int cards[13] = {101,112,109,107,202,209,
					 213,212,313,303,403,412,402};
	int last_card = 7;
	int min = 14;
	int pos = -1;
	for (int i =0; i < 13; i++)
		if ((cards[i] % 100) > 7)
			if ((cards[i] % 100) < min)
			{
				pos = i;
				min = cards[i] % 100;
		}
	if (pos != -1)
		cout << "比" << last_card << "大的最小牌是第" 
			 << pos + 1 << "張牌" <<endl;
	else 
		cout << "沒找到" <<endl; 
	return 0; 
}

注意到，本例中有兩張 9 均符合結果，判定為 小于 是以輸出的是第一個符合條件的牌的位置

4.4 折半查找

筆記

  已知查找目标是有序排列的

  選擇目标最中間的資料作為判定目标，每次判定篩選掉一半資料，是以是折半查找

初始化-->選取中間資料判定-->找到跳出，未找到更新範圍-->範圍内無牌-->輸出

代碼實作 

#include <iostream>
using namespace std;

int main() 
{
	int target_card = 112; 
	int cards[13] = {101,107,109,112,202,209,
					 212,213,303,313,402,403,412};
	int pos = -1;
	int low = 0, high = 12;
	while (low <= high)
	{
		int middle = (low + high) / 2;
		if (cards[middle] == target_card)
		{
			pos = middle;
			break;
		}
		else if (cards[middle] > target_card)
			high = middle -1;
		else
			low = middle +1;
	}
	if (pos != -1)
		cout << target_card << "是第" 
			 << pos + 1 << "張牌" <<endl;
	else 
		cout << "沒找到" <<endl; 
	return 0; 
}

4.5 排序問題

筆記

  插入排序：将第 i 個元素 插入 之前的資料中的比自己大的資料之前

  選擇排序： 選取 第 i 個之後的最小值放在 i 的位置

  折半插入排序：在插入排序中，第 i 個元素之前的資料已經被排序，是以進行插入時可以使用折半查找

4.5.1 代碼實作 

//插入排序 
#include <iostream>
using namespace std;

int main() 
{
	int cards[13] = {101,112,109,107,202,209,
					 213,212,313,303,403,412,402};
	for (int i =0; i < 13; i++)
	{
		int pos = -1, min = 500, target = cards[i];
		for (int j = 0; j < i; j++)
			if(cards[j] > target)
				if(cards[j] < min)
				{
					min = cards[j];
					pos = j;
				}
		if (pos != -1)
		{
			for (int j = i; j >pos; j--)
				cards[j] = cards[j - 1];
			cards[pos] = target;
		}
	}
	for (int i =0; i < 13; i++)
		cout << cards[i] << " ";
	cout <<endl;
	return 0; 
}

4.5.1 代碼簡化

  因為第 i 個資料之前的值，已經從小到大排列過，是以當按照順序找到的第一個比 cards[i] 大的數時，這個數肯定是期望的最小數，是以可以簡化掉對 min 的處理

for (int i =0; i < 13; i++)
	{
		int pos = 0, target = cards[i];
		while (target > cards[pos])
			pos++;
		for (int j = i; j >pos; j--)
			cards[j] = cards[j - 1];
		cards[pos] = target;
	}

4.5.2 代碼實作 

//選擇排序 
#include <iostream>
using namespace std;

int main() 
{
	int cards[13] = {101,112,109,107,202,209,
					 213,212,313,303,403,412,402};
	for (int i =0; i < 13; i++)
	{
		int min = cards[i],pos = i;
		for (int j = i + 1; j < 13; j++)
			if (cards[j] < min)
			{
				min = cards[j];
				pos = j;
			}
		cards[pos] = cards[i];
		cards[i] = min;
	}
	for (int i =0; i < 13; i++)
		cout << cards[i] << " ";
	cout <<endl;
	return 0; 
}

4.5.3 代碼實作 

//函數寫法 
#include <iostream>
using namespace std;

void insertsort(int cards[], int n);
void selectsort(int cards[], int n);

int main() 
{
	int cards[13] = {101,112,109,107,202,209,
					 213,212,313,303,403,412,402};
	
//	insertsort(cards, 13);
	selectsort(cards, sizeof(cards) / sizeof(int));

	for (int i =0; i < 13; i++)
		cout << cards[i] << " ";
	cout <<endl;
	return 0; 
	return 0; 
}

void insertsort(int cards[], int n)
{
	for (int i =0; i < n; i++)
	{
		int pos = 0, target = cards[i];
		while (target > cards[pos])
			pos++;
		for (int j = i; j >pos; j--)
			cards[j] = cards[j - 1];
		cards[pos] = target;
	}
}

void selectsort(int cards[], int n)
{
	for (int i =0; i < n; i++)
	{
		int min = cards[i],pos = i;
		for (int j = i + 1; j < n; j++)
			if (cards[j] < min)
			{
				min = cards[j];
				pos = j;
			}
		cards[pos] = cards[i];
		cards[i] = min;
	}
}

4.5.3 代碼拓展

  數組的長度，使用 sizeof() 提取數組長度，因為數組是一個 int 類型的數組，是以需要除以 sizeof(int) 才是最終的數組長度。

4.5.4 代碼實作 

//折半插入排序 
#include <iostream>
using namespace std;

int main() 
{
	int cards[13] = {101,112,109,107,202,209,
					 213,212,313,303,403,412,402};
	for (int i =0; i < 13; i++)
	{
		int pos = -1,target = cards[i];
		int low = 0, high = i - 1;
		while (low <= high)
		{
			int middle = (low + high) / 2;
			if((cards[middle] < target) && (cards[middle + 1] > target))
			{
				pos = middle + 1;
				break;
			}
			else if (cards[middle] > target)
				high = middle -1;
			else
				low = middle +1;
		}
		if (pos != -1)
		{
			for (int j = i; j >pos; j--)
				cards[j] = cards[j - 1];
			cards[pos] = target;
		}
	}
	for (int i =0; i < 13; i++)
		cout << cards[i] << " ";
	cout <<endl;
	return 0; 
}

文法自測-試題答案

學堂線上-程式設計基礎-第四章第四章-篩法與查找
學堂線上-程式設計基礎-第四章第四章-篩法與查找
學堂線上-程式設計基礎-第四章第四章-篩法與查找
學堂線上-程式設計基礎-第四章第四章-篩法與查找

本題中 i-j 為負數

學堂線上-程式設計基礎-第四章第四章-篩法與查找
清華大學 學堂線上 程式設計基礎 mooc 程式設計 c++
上一篇: Redis 安裝+三種啟動設定（開機自啟動）
下一篇: java手動處理異常方式_java 異常之手動抛出與自動抛出的執行個體講解

繼續閱讀