// 之前判断素数, 只需要到sqrt(x)即可,
//更加简单的, 判断能够比已知的小于x的素数整除, 运行更快
#include <stdio.h>
// 之前判断素数, 只需要到sqrt(x)即可,
//更加简单的, 判断能够比已知的小于x的素数整除, int isprime(int x,int knownprimes[],int n)
{
int ret=;
int i;
for (i=;i<n;i++){
if (x%knownprimes[i]==){
ret=;
break; //不是素数
}
}
return ret;
} int main(void)
{
const int num=;// 想要输出几个素数
int prime[num]={}; //存放素数
int i=;
int cnt=; // 增加一个表头, 表示列数
{
printf("\t\t");
for (int i=;i<num;i++){
printf("%d\t",i);
}
printf("\n");
}
// 以上表头 while(cnt<num){
if (isprime(i,prime,cnt)){
prime[cnt++]=i; // 这个表达式将 i写入到cnt位置, 又使其+1
}
// 增加调试 用一对{}括起来
{
printf("i=%d\tcnt=%d\t",i, cnt);
for(int i=;i<num;i++) {
printf("%d\t",prime[i]);
}
printf("\n");
}
// 调试 i++;// 测试下一个i
}
for (i=;i<num;i++){
printf("%d",prime[i]);
if((i+)%) printf("\t");
else printf("\n");
}
return ;
}
那么如何构造素数表?.. (划线法) .. 想要构造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的数组isprime[30]
int x;
int isprime[num];
int i;
for(i=;i<num;i++){
isprime[i]=;
} // 初始化prime 数组, 设置为1 for (x=;x<num;x++){
if (isprime[x]){
for (i=;i*x<num;i++)
isprime[i*x]=;
} // x是素数则 它的倍数都不是素数 标记为0
} for (i=;i<num;i++){ // 从i=2位置开始进行输出
if (isprime[i]==){
printf("%d\t",i);
} } //输出素数
printf("\n");
return ;
}
(一) 搜索实例, (美元不同币值称呼不同)
#include<stdio.h>
// penny 1; nickel 5; dime 10; quarter 25; half-dollar 50
int a[]={,,,,};
char *name[]={"penny","nickel","dime","quarter","half-dollar"};// 这里的* 必须要有, 否则出错! int search(int key, int a[],int len )
{
int ret=-;
for(int i=;i<len;i++){
if (key==a[i]){
ret=i;
break;
}
}
return ret;
} int main()
{
int k=;
int r=search(k,a,sizeof(a)/sizeof(a[]));
if (r>-){
printf("%s\n",name[r]); // 输出k表示的美元货币名字
} return ;
}
结果是dime.
但是这样缺点在于需要用到两个数组, 如何做到只需要一个数组? ...用struct
#include<stdio.h>struct{
int a;
char *name; // * 必须要有, 否则出错!
} coins[]={
{,"penny"},
{,"nickel"},
{,"dime"},
{,"quarter"},
{,"half-dollar"}
};
int main()
{
int k=;
for (int i=;i<sizeof(coins)/sizeof(coins[]);i++){
if (k==coins[i].a){
printf("%s\n",coins[i].name);
break;
}
}
return ;
}
之前这种线性搜索很慢, 如果要搜索的值为数组的最后一个, 则需要全部遍历, 不好, 可以用二分法进行搜索, 确定left ,right ,mid , 缩小范围
但二分法的前提是数据已经从小到大排好了, 先假设数组中的元素已经按照升序排好了
#include<stdio.h>
int search(int key,int a[],int len)
{
int left=;
int right=len-;// 最大下标是长度-1
int ret=-; // 判别是否找到,记录位置
while(left<=right)
{
int mid=(left+right)/;
if(a[mid]==key){
ret=mid;
break;
}else if(a[mid]>key){
right=mid-;
}else{
left=mid+;
}
}
return ret;
}
int main()
{
int a[]={,,,,,};
int k=;
int loc=search(k,a,sizeof(a)/sizeof(a[]));
printf("%d",loc);
return ;
}
上述要找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=;
for(int i=;i<len;i++){
if (a[i]>a[maxid]){
maxid=i;
}
}
return maxid;
} int main()
{
int a[]={,,,,,,,,};
int len=sizeof(a)/sizeof(a[]);
for (int i=len-;i>;i--)
{
int maxid=max(a,i+);// 找到最大的
// swap a[maxid] and a[len-1]
int t=a[maxid];
a[maxid]=a[i];
a[i]=t;
}
// 输出排序后的结果
for(int i=;i<len;i++){
printf("%d ",a[i]);
}
return ;
}