程式設計-- Binary Search 通訊一甲 B09622048 楊穎穆.

Slides:



Advertisements
Similar presentations
While 迴圈 - 不知重複執行次數
Advertisements

《C语言程序设计》复习
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
“八皇后”问题 崔萌萌 吕金华.
请将手机调整到静音状态 实验网站:program3.ccshu.net 资源网站:class.ccshu.org/ /
C语言程序设计 第十二章 位运算.
C语言程序设计 课程 第5章 数组 主讲:李祥 博士、副教授 单位:软件学院软件工程系.
高级语言程序设计 主讲人:陈玉华.
第一章 C语言概述.
C 程序设计实例 1. 问题描述 2. 数据结构 3. 算法分析 4. 参考程序 5. 改进说明.
Do.For.While.正三角.倒正三角.倒九九乘法表
選擇排序法 通訊一甲 B 楊穎穆.
C的發展史 C程式初體驗 C程式設計基本注意事項 上機實習課程
適用於多選一 可減少if 與 else配對混淆的錯誤.
If … else 選擇結構 P27.
Chap 2 用C语言编写程序 2.1 在屏幕上显示 Hello World! 2.2 求华氏温度 100°F 对应的摄氏温度
搜尋資料結構 Search Structures.
使用VHDL設計—4位元加法器 通訊一甲 B 楊穎穆.
Introduction to the C Programming Language
Introduction to the C Programming Language
使用VHDL設計—4位元位移器 通訊一甲 B 楊穎穆.
STRUCTURE 授課:ANT 日期:2010/5/12.
计算概论 第十八讲 C语言高级编程 结构与习题课 北京大学信息学院.
程式撰寫流程.
第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
電子學實驗—自給偏壓共射極放大 通訊二甲 B 楊穎穆.
Introduction to the C Programming Language
作弊是否很有诱惑性? 上堂课已经讲了 作业不一定在两个小时里都能完成 答疑没有一个人? 作弊是有记录的 心理系很多同学集体作弊,让人震惊
C语言 程序设计基础与试验 刘新国、2012年秋.
多维数组与指针 用指针变量可以指向一维数组中的元素,也可以指向多维数组中的元素。但在概念上和使用上,多维数组的指针比一维数组的指针要复杂一些。 1. 多维数组元素的地址 先回顾多维数组的性质,可以认为二维数组是“数组的数组”,例 : 定义int a[3][4]={{1,3,5,7},{9,11,13,15},{17,19,21,23}};
使用VHDL設計-多工器/解多工器 通訊一甲 B 楊穎穆.
計數式重複敘述 for 迴圈 P
第0章作业: 教材P12-练习与实践 1.写出用符号’*’输出描绘汉字”大”的流程图。
邏輯設計--不穩多諧振盪器 通訊一甲 B 楊穎穆.
電子學實驗--CE放大電路 通訊二甲 B 楊穎穆.
資料結構與C++程式設計進階 排序與搜尋 講師:林業峻 CSIE, NTU 6/ 14, 2010.
使用VHDL設計 七段顯示器 通訊工程系 一年甲班 姓名 : 蘇建宇 學號 : B
C语言复习2----函数.
程式設計期末測驗 通訊一甲 B 楊穎穆.
Main() { Dfas Asdfasf fasdfa } #include <stdio.h> void main( ) {
Introduction to the C Programming Language
共源極頻率響應 科系:通訊工程學系 執導老師:王志湖 學號:B 姓名:何信賢.
Chap 5 函数 5.1 计算圆柱体积 5.2 使用函数编写程序 5.3 变量与函数.
輸出與輸入(I/O).
C qsort.
資料結構與C++程式設計進階 遞迴(Recursion) 講師:林業峻 CSIE, NTU 6/ 17, 2010.
第一章 C语言概述 目录 什么是语言、程序 C语言的历史与发展 C语言的书写形式与程序结构 运行C语言的步骤与方法
实验七 数 组 第21讲 C程序设计 Main() { int x,y; X=10; y=x*x+1;
Introduction to the C Programming Language
自停式向下計數器 通訊一甲 B 楊穎穆.
陣列與結構.
元 排 序 法.
程式設計--linear search 通訊一甲 B 楊穎穆.
電子學實驗—共集極放大電路 通訊二甲 B 楊穎穆.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
使用VHDL設計-8x3編碼電路 通訊一甲 B 楊穎穆.
可變式計數器 通訊一甲 B 楊穎穆.
程式設計--Quick Sort 通訊一甲 B 楊穎穆.
查表法&電腦IO Port二進制轉七段顯示器
多重條件選擇敘述
C/C++基礎程式設計班 陣列 講師:林業峻 CSIE, NTU 3/14, 2015.
使用VHDL設計-七段顯示 通訊一甲 B 楊穎穆.
Array(陣列) Anny
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
C語言程式設計 老師:謝孟諺 助教:楊斯竣.
函式庫補充資料 1.
C语言基础学习 从外行到入门.
微 處 理 機 專 題 – 8051 C語言程式設計 主題:階乘計算
隨機函數.
Presentation transcript:

程式設計-- Binary Search 通訊一甲 B09622048 楊穎穆

目錄 1.目的 2.原理 3.流程圖 4.程式 5.實驗結果顯示 6.參考資料

目的 1. 試輸入n個未排序的整數到陣列中 2. 嘗試把未排序的整數到陣列中之數值依照陣列位置與值印出 3. 嘗試用快速排序(Quick Sort)法把陣列中之數值由小而大地排序 4. 嘗試把排序後的整數到陣列中之數值依照陣列位置與值印出 5. 試輸入一個陣列中的值,使用二元搜尋(Binary Search)找到此值在陣列的所在位置並把此位置印出

原理 假如資料本身是經過排序的,在搜尋時可以利用二元的方法,每次都把陣列分成兩半,然後從其中的一半繼續搜尋,這種方法叫做「二元搜尋」(Binary search),首先,陣列裡的元素要排序,然後等分成兩個陣列,由於陣列已排序過,搜尋的值只會存在於其中的一個陣列中,只要比較搜尋鍵和二元陣列中的極值(也就是最大值或最小值),就知道要搜尋的值位於那個陣列中,然後繼續在那個陣列中進行二元搜尋。

原理 11 6 8 16 3 A[0] A[1] A[2] A[3] A[4] 3 6 8 11 16

流程圖 main Input x L<=R i= (L+R)/2 X=A[i] 印出 i L=i R=i end

程式 #include <stdio.h> #include <stdlib.h> #define n 8 int Partition(int a[],int p, int r){ int s,j,temp; int x=a[r]; int i=p-1; for(j=p;j<r;j++){ if(a[j]<=x){ i++; if(i !=j){ temp=a[i]; a[i]=a[j]; a[j]=temp; }

temp=a[i+1]; a[i+1]=a[j]; a[j]=temp; printf("\n"); for(s=0;s<n;s++) printf(" %d",a[s]); return i+1; } int quicksort(int a[],int p,int r){ int q; if(p<r){ q=Partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,p);

int main(void){ int t,A[n],i,x; int l,r,mid; for(t=0;t<n;t++){ printf(" 請輸入任意數字[%d]:",t); scanf("%d",& A[t]); } quicksort(A,0,n-1); printf("\n由小到大排序後的數字[%d]: ",t); printf("%d \n",A[t]);

printf("\n隨意輸入一個數:"); scanf("%d",&x); l=0; r=9; mid=l+(r-l)/2; while((l<r)&&(A[mid]!=x)){ if(A[mid]>x) r=mid-1; else if(A[mid]<x) l=mid+1; } if(A[mid]==x) printf("位址在 A[%d]",mid); else printf("\n找不到"); system("PAUSE"); return 0;

實驗結果顯示

實驗結果顯示

實驗結果顯示

參考資料 主要的參考資料來至”演算法概論”這本書及王志湖老師上課所教授的內容。

END