// 之前判断素数, 只需要到sqrt(x)即可,
//更加简单的, 判断能够比已知的小于x的素数整除, 运行更快
#include <stdio.h> // 之前判断素数, 只需要到sqrt(x)即可, //更加简单的, 判断能够比已知的小于x的素数整除, int isprime(int x,int knownprimes[],int n) { int ret=1; int i; for (i=0;i<n;i++){ if (x%knownprimes[i]==0){ ret=0; break; //不是素数 } } return ret; } int main(void) { const int num=10;// 想要输出几个素数 int prime[num]={2}; //存放素数 int i=3; int cnt=1; // 增加一个表头, 表示列数 { printf(" "); for (int i=0;i<num;i++){ printf("%d ",i); } printf(" "); } // 以上表头 while(cnt<num){ if (isprime(i,prime,cnt)){ prime[cnt++]=i; // 这个表达式将 i写入到cnt位置, 又使其+1 } // 增加调试 用一对{}括起来 { printf("i=%d cnt=%d ",i, cnt); for(int i=0;i<num;i++) { printf("%d ",prime[i]); } printf(" "); } // 调试 i++;// 测试下一个i } for (i=0;i<num;i++){ printf("%d",prime[i]); if((i+1)%5) printf(" "); else printf(" "); } return 0; }
那么如何构造素数表?.. (划线法) .. 想要构造n以内的素数表,
1.令x为2,
2.将小于n的2x 3x 4x...的数标记为非素数,
3.令x 为下一个没有被标记为非素数的数, 重复2; 直到所有的数都尝试完毕.
算法:
1.开辟prime[n], 初始化全为1, prime[x]=1表示x是素数,
2.令x=2;
3. 如果x是素数, 对于(i=2;i*x<n;i++) 令prime[i*x]=0;
4.x++, 如果x<n 重复3, 否则结束
程序如下
#include<stdio.h> int main() { const int num=30;// 找30 以内的素数 , 则建立一个长度是30的数组isprime[30] int x; int isprime[num]; int i; for(i=0;i<num;i++){ isprime[i]=1; } // 初始化prime 数组, 设置为1 for (x=2;x<num;x++){ if (isprime[x]){ for (i=2;i*x<num;i++) isprime[i*x]=0; } // x是素数则 它的倍数都不是素数 标记为0 } for (i=2;i<num;i++){ // 从i=2位置开始进行输出 if (isprime[i]==1){ printf("%d ",i); } } //输出素数 printf(" "); return 0; }
(一) 搜索实例, (美元不同币值称呼不同)
#include<stdio.h> // penny 1; nickel 5; dime 10; quarter 25; half-dollar 50 int a[]={1,5,10,25,50}; char *name[]={"penny","nickel","dime","quarter","half-dollar"};// 这里的* 必须要有, 否则出错! int search(int key, int a[],int len ) { int ret=-1; for(int i=0;i<len;i++){ if (key==a[i]){ ret=i; break; } } return ret; } int main() { int k=10; int r=search(k,a,sizeof(a)/sizeof(a[0])); if (r>-1){ printf("%s ",name[r]); // 输出k表示的美元货币名字 } return 0; }
结果是dime.
但是这样缺点在于需要用到两个数组, 如何做到只需要一个数组? ...用struct
#include<stdio.h>struct{ int a; char *name; // * 必须要有, 否则出错! } coins[]={ {1,"penny"}, {5,"nickel"}, {10,"dime"}, {25,"quarter"}, {50,"half-dollar"} }; int main() { int k=10; for (int i=0;i<sizeof(coins)/sizeof(coins[0]);i++){ if (k==coins[i].a){ printf("%s ",coins[i].name); break; } } return 0; }
之前这种线性搜索很慢, 如果要搜索的值为数组的最后一个, 则需要全部遍历, 不好, 可以用二分法进行搜索, 确定left ,right ,mid , 缩小范围
但二分法的前提是数据已经从小到大排好了, 先假设数组中的元素已经按照升序排好了
#include<stdio.h> int search(int key,int a[],int len) { int left=0; int right=len-1;// 最大下标是长度-1 int ret=-1; // 判别是否找到,记录位置 while(left<=right) { int mid=(left+right)/2; if(a[mid]==key){ ret=mid; break; }else if(a[mid]>key){ right=mid-1; }else{ left=mid+1; } } return ret; } int main() { int a[]={1,3,5,6,8,10}; int k=3; int loc=search(k,a,sizeof(a)/sizeof(a[0])); printf("%d",loc); return 0; }
上述要找k=3 所在的位置, 开始left=0,right=5, mid=2, 之后 left=0, right=1, mid=0; 之后left=1, right=1, 终止循环, 但是没有输出啊, 函数中ret=-1没有改变过!!
这是怎么回事?
接下来考虑如何排序问题,,,
我们用选择法 进行排序
#include<stdio.h> // 排序 // 思路, 找到数组中找出最大的值的位置; // 交换位置, 将最大值与数组的最后一个位置的值交换; // 剩下的n-1长度的继续找最大的, int max(int a[],int len) { int maxid=0; for(int i=0;i<len;i++){ if (a[i]>a[maxid]){ maxid=i; } } return maxid; } int main() { int a[]={2,24,12,38,58,92,15,90,29}; int len=sizeof(a)/sizeof(a[0]); for (int i=len-1;i>0;i--) { int maxid=max(a,i+1);// 找到最大的 // swap a[maxid] and a[len-1] int t=a[maxid]; a[maxid]=a[i]; a[i]=t; } // 输出排序后的结果 for(int i=0;i<len;i++){ printf("%d ",a[i]); } return 0; }