Learn And Life.

算法

Posted on

矩阵求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#include<stdlib.h>             
void  makeMatrix(int len,int data[]){ 
    int i,j;                   
    //初始化矩阵               
    for(i =2;i<len;i++){       
        data[i] = 1;           
    }
    for(i =2; i<len; i++){     
        if(data[i]){           
            for(j=i; i*j < len; j++){       
                data[i*j] = 0; 
            }
        }                      
    }
} 
int main(int argc, char **argv){
    int N = atol(argv[1]);
    int *data = malloc(N * sizeof(int));
    if(data == NULL){
        printf("Insufficient memory.\n");
        return -1;
    }                                                                                                                                                                              
    makeMatrix(N,data);
    for(int i =2 ; i < N; i++){
        if(data[i]){    
             printf("%4d ", i);              
        }
    }
    printf("\n");
    return 0;
}

该方法使用0和1，通过构建数组的方式，使用动态内存分配的方式，来求素数

二分查找

问题：一个有序序列，如何找到绝对值最小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<stdlib.h>
int binSearch(int data[], int low, int high)
{
   int mid = low + (high - low) / 2;
   if(low > high) {
       return -1;
   }
   if(data[low] < 0 && data[high] < 0) {
       return high;
   }
   if(data[low] > 0) {
       return low;
   }
   while(1) {
        if(data[mid-1] < 0 && data[mid+1] > 0){
           return mid;
        }
        if(data[mid] > 0){
           high = mid;
        }else{
           low = mid;
        }
        mid = low + (high - low) / 2;
   }
   return -1;
}
void dumpAbsMin(int data[], int low, int high)
{
    int mid = binSearch(data, low, high);
    if (mid < 0) {
                                                                                                                             1,1          顶端
  printf("an error happend\n");
       return;
    }else{
       printf("%d %d \n", mid, data[mid]);
    }
    int left = mid, right = mid;
    while(abs(data[right]) == abs(data[right+1])){
        right++;
        printf("%d %d \n", right, data[right]);
    }
    while(abs(data[left]) == abs(data[left-1])){
        left--;
        printf("%d %d \n", left, data[left]);
    }
}
int main(int argv, char **argc){
  int data[] = {-9,-8,-3,-2,-1,-1,-1,-1,1,1,1,1,3,6,19};
  dumpAbsMin(data, 0, 8);
  return 0;
}

输出:

1
2
3
4
5
6
7
8
9
root@chenjingxiu:~/project/algorithm# ./d
7 -1 
8 1 
9 1 
10 1 
11 1 
6 -1 
5 -1 
4 -1

输出了所有的绝对值等于1的元素，但是这个问题有哪些需要注意的呢？

1
2
3
4
1. 整形溢出. 如果使用mid = (high + low) / 2计算mid，当high+low超过了整形的范畴，就会溢出;
2. 数据序列. 序列是否都是正数，负数，还是正负数都有，针对不同的情况，处理方式就不一样
3. 多个绝对值相等元素. 如果序列中存在多个绝对值相等的元素如何处理
4. 如果找到正负之间的元素，通过其左右两边的元素的正负来判定，这是重点