作者gna239 ( Kaonashi)
看板C_and_CPP
標題Re: [問題] 二元搜尋法
時間Fri May 15 00:30:30 2009
#include <iostream>
#include <stdio.h>
#include <cstdlib>
using namespace std;
int BinarySearch(int *Array, int keyword, int left, int right);
int CheckNum(int *Array,int number,int count);
int CheckSameNumber(int mark,int *Array,int number);
int main()
{
FILE *fptr;
//Read Grades.txt
fptr = fopen("Grades.txt","r");
if(!fptr)
{
printf("No such file found!\n");
system("pause");
return 0;
}
//Scores Store into the array Grades
int index = 0;
int Grades[30];
while(!feof(fptr))
{
fscanf(fptr,"%d",&Grades[index++]);
}
printf("UnSorted numbers :\n");
for(int i=0;i<index;i++) printf("%3d ",Grades[i]);
// Selection Sort
int temp = 0;
int i,j,min;
for(i=0;i<index-1;i++)
{
min=i;
for(j=i+1;j<index;j++)
{
if(Grades[min]>Grades[j])
{
min=j;
}
}
temp=Grades[min];
Grades[min]=Grades[i];
Grades[i]=temp;
}
//End Selection Sort
//Display the Array Grades After Selection Sort
printf("\nSorted numbers :\n");
for(i=0;i<index;i++) printf("%3d ",Grades[i]);
int input;
int rank = 0;
int count=1; //計算輸入次數變數
printf("\nPlease enter the score what you want to search:");
scanf("%d",&input);
//判斷輸入值是否落在0~100
while( input<0 || input>100)
{
if(count==3) //輸入錯誤三次以上，結束程式
{
printf("\nThe input score is invalid.\n");
system("pause");
return 0;
}
printf("\nThe input score is invalid.");
printf("\nPlease enter a new score:");
scanf("%d",&input);
count++;
}
//判斷輸入值是否在Array Grades裡
int Check;
Check = CheckNum(Grades,input,index);
if(Check==1)
{
rank = BinarySearch(Grades, input, 0, index);
printf("The rank of the score is: %d\n",index-rank);
printf("The number of the score is:%d\n",CheckSameNumber(rank,Grades,index));
}
else
{
printf("\nThe input score is invalid.");
printf("\nPlease enter a new score:");
scanf("%d",&input);
count++;
}
system("pause");
fclose(fptr);
return 1;
}
//判斷是輸入值是否在陣列中
int CheckNum(int *Array,int number,int count)
{
for(int i=0;i<count;i++)
{
if(Array[i]==number)
{
return 1;
}
}
return 0;
}
//二元搜尋法
int BinarySearch(int *Array, int keyword, int left, int right)
{
int middle;
right=right-1;
while(left<=right)
{
middle=(left+right)/2;
if(keyword==Array[middle])
{
return middle;
}
else if(keyword<Array[middle])
{
right=middle-1;
}
else if(keyword>Array[middle])
{
left=middle+1;
}
}
return -1;
}
//判斷此相同分數的有幾個
int CheckSameNumber(int mark,int *Array,int number)
{
int count=0;
int i;
for(i=0;i<number;i++)
{
if(Array[i]==Array[mark])
{
count++;
}
}
return count;
}
說真的有點長....
忘了怎麼修文 只好再PO一篇= ="
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.252.6
1F：推 Peruheru:Shift + E 05/15 11:51