陣列(2)陣列運算及典例(求解素數的方法)

2023-11-28 21:01:35

<1>陣列運算

1)陣列的整合初始化

  • 1.形式範例

1 - int a[]={1,2,3...};
2 - int a[13]={2};————第一個單元內中的a0=2,剩下的單元都預設賦為0

  • 2.整合初始化時的定位——僅適用於C99

舉例:

int a[10]={ [0]=2,[2]=3,6, };

特點:
  1. 用[n]在初始化資料中給出定位;
  2. 沒有定位的資料接在前一個單元之後;
  3. 其餘位置補0;
  4. 也可以不給出陣列大小讓編譯器算;

2)陣列的大小

————sizeof給出整個陣列所佔據的內容的大小,單位是位元組

  • 用sizeof陣列除以sizeof陣列的第一個單元,就得到陣列的元素個數

——sizeof(a)/sizeof (a[0])

  • 這樣的程式碼,即使陣列中的初始資料被修改,也不需要
    修改遍歷程式碼

3)陣列的賦值

  • 範例:

int a[]={1,2,3,4...};
int b[]=a;

  • 判斷:

————判斷這串程式碼是否可以實現將a的陣列賦給b的陣列
  • 結果及原因

1.結果:陣列不能實現將一個陣列變數賦給另一個陣列變數;
2.原因:要實現將一個陣列的所有元素交給另一個陣列,必須通過遍歷;

  • 範例:
    for(i=0;i<length;i++){
    b[i]=a[i];
    }

4)補充:遍歷陣列

  • 1.一般形式

    通常使用for迴圈,讓迴圈變數i從0到小於陣列的長度,這樣迴圈體內最大的i正好是陣列最大的有效下標
  • 2.常見錯誤:

    1-迴圈結束條件為<=陣列長度;
    2-離開回圈後,繼續用i的值來做陣列元素的下標;————正好是陣列無效的下標
  • 3.陣列作為函數引數時,必須再使用另外一個引數來傳入陣列的大小

注意:

  1. 當陣列作為函數引數時,不能在[]中給出陣列的大小;
  2. 同時也不能再利用sizeof來計算陣列的元素個數;

<2>陣列典例:素數

  • 求解素數的幾種方法

(1)呼叫函數

int isprime(int x);
int main(void){
int x;
scanf("%d",&x);
if(isprime(x)){
printf("%d是素數\n",x);
}else{
printf("%d不是素數\n",x);
}
}return 0;

(2)從2到x-1測試是否可以整除

int isprime(int x){
int ret=1;
int i;
if(x= =1) ret = 0;
for(i=2;i<x;i++){
if(x%i==0){
ret=0;
break;
}
}
return ret;
}

  • 對於n要回圈n-1遍;
  • 當n足夠大時,就是n遍;

(3)去掉偶數後,從3開始到x-1,每次加2

int isprime(int x){
int ret=1;
int i;
if(x= =1||(x%2==0&&x!=2))
ret=0;
for(i=3;i<x;i+=2){
if(x%i= =0){
ret=0;
break;
}
}
return ret;
}

  • 當n很大時迴圈次數為n/2次

(4)對(3)進行進一步修改,無需達到x-1次,使用sqrt(x)

int isprime(int x){
int ret=1;
int i;
if(x= =1||(x%2==0&&x!=2))
ret=0;
for(i=3;i<sqrt(x);i+=2)
if(x%i= =0){
ret=0;
break;
}
}
return ret;
}

  • 只需迴圈sqrt(x)次

(5)構建素數表

int main (void){
const int number=100;//計算前一百位素數
int prime [number]={2};** //初始化為2**
int count=1;//已經包含了一個元素2;
int i=3;
while(count<number){
if (isprime(i,prime,count)){
prime[count++]=i;

//對cnt變數進行理解:

  • cnt變數的值為1,1對應陣列下標1所在的位置,所以prime[cnt++]=i我們是將i的值當第一次i=3寫到cnt對應的位置上去;這之後在進行++操作,這時cnt便等於2,也就意味著cnt指向了陣列中下標為2的位置(即分為兩個操作:1:將cnt的值賦到對應位置;2:將cnt指向下一個位置)

}
i++;
}
for(i=0;i<number;i++){
printf("%d",prime[i]);
if((i+1)%5) printf("\t");
else printf("\n");
}
return 0;
}

(6)進一步改造素數表

  • 規則(構造n以內的素數表)

1. 令x=2;
2. 將2x,3x,4x...直至ax<n的數標記為非素數;
3. 令x成為下一個沒有被標記的非素數的數,重複2的操作,直到所有數被嘗試完畢;

  • 我們舉例對方法進行理解

1.陣列:2,3,4,5,6,7,8,9,10,11,12,13
2.推理過程:

第一項為2,2的倍數有4,6,8,10,12,將這些數標記為非素數,此時剩下的沒有被標記的非素數為3,5,7,9,11,13;
接著以3為x,3的倍數6,9,12被標記為非素數;此時剩下的沒有被標記的非素數還有5,7,11,13;
以此類推……

(7)再次改造,運用虛擬碼

  • 目的:構造n以內的素數表

  • 思路:

1. 開闢prime[n],初始化其所有元素為1,prime[x]為1表示x是素數;
2. 令x=2;
3. 如果x是素數,則對於(i=2;xi<n;i++),令prime[ix]=0;
4. 令x++,如果x<n,重複3,否則結束

  • 程式碼

#include <stdio.h>

int main(){
const int maxnumber=25;
int isprime[maxnumber];
int i;
int x;
for(i=0;i<,maxnumber;i++){
isprime[i]=1;//————1.初始化所有元素為1————
}
for(x=2;x<maxnumber;x++){
if(isprime[x]){
for(i=2;ix<maxnumber;i++){
isprime[i
x]=0;//————2.將所有該數的倍數標記為0,也就是標記為非素數————
//————3.同時再對下一個素數進行同樣的操作,對小於maxnumber的數進行遍歷————
}
}
}
for(i=2;i<maxnumber;i++){
if(isprime[i]){
printf("%d\t",i);//————4.將所有是素數的數,isprime仍保留為1的進行輸出————
}
}
printf("\n");
return 0;

}