個人資訊
郭怡勝
訪客 (22638), 推薦 (1)
文章 (95)
回應 (1)
Meeeeeeee
隨堂筆記
程式語言 (2)
最新回應
re: 106/09/26作業(身高及體重加減) (09-26, 龔鈺晟)
隨機產生n數排序找尋
by 郭怡勝
2018-01-02 11:28:33, 回應(0), 人氣(338)
2018-01-02 11:28:33, 回應(0), 人氣(338)
/*
隨機產生n個(1-20000)的0-30000相異整數
比較排序前後以so%%
1.線性找尋(未排序)
2.線性找尋(排序)
2.二分找尋 某一整數的次數
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int a[30001],left,right,middle,no;
int i, j, t,N,flag,x,key,found=0,nn;
long tk;
unsigned seed;
seed = (unsigned)time(NULL);
srand(seed);
printf("正修科大 40404113 郭怡勝\n");
printf("請輸入模擬數目(<=20000):");
scanf("%d",&N);
for(i=0; i<N; i++)
{
while(1)
{
flag=1;
x = rand() % 30001;
for(j=0;j<=i-1;j++)
{
if( x == a[j])
{
flag=0;
break;
}
}
if(flag == 1)
{
a[i]=x;
break;
}
}
}
printf("\n原陣列：\n");
for (i=0; i<N; i++) printf("%6d",a[i]);
printf("\n未排序(線性找尋)：\n");
printf("\n\n請輸入要找的值:");
scanf("%d",&key);
for(i=0;i<N;i++)
{
if(key == a[i])
{
found=1;
break;
}
}
if(found == 1)
printf("\n找了 %3d 次，找到了\n",i+1);
else
printf("\n找了 %3d 次，找不到\n",i);
printf("\n排序後(線性找尋)：\n");
printf("\n");
for (i=0; i<N-1; i++)
for (j=i+1; j<N; j++)
if (a[i]>a[j])
{
t = a[j];
a[j] = a[i];
a[i] = t;
}
printf("\n\n排序後\n");
for (i=0; i<N; i++) printf("%6d",a[i]);
printf("\n");
for(i=0;i<N;i++)
{
if(key == a[i])
{
found=1;
break;
}
}
if(found == 1)
printf("\n找了 %3d 次，找到了\n",i+1);
else
printf("\n找了 %3d 次，找不到\n",i);
printf("\n二分找尋：\n");
printf("\n");
for (i=0; i<=N; i++)
{
for (j=0; j<=N-i; j++)
if (a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
left=0;
right=N;
while (left <= right)
{
middle=(left+right)/2;
no++;
if (key < a[middle])
right=middle-1;
else if (key > a[middle])
left=middle+1;
else if (key==a[middle])
break;
}
if (key==a[middle])
printf("\n找了 %d 次, %d 在第 %d 個位置找到\n",no, key,middle-1);
else
printf("\n找了 %d 次, %d 找不到\n",no, key);
return 0;
}