1 Multi-dimensional arrays

  • Understanding the relationship between one dimensional arrays and two- or multi-dimensional arrays
  • An example
// One- and multi-dimensional array
#include<stdio.h>
#include<stdlib.h>
int main(){
    int i,j,k, a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};
    printf("a=\n");
    for(i=0;i<3;i++)
        for(j=0;j<4;j++)
            printf("%d\t",a[i][j]);
    printf("\n");

    printf("a=\n");
    for(i=0;i<3;i++)
        printf("%p\t",a[i]);
    printf("\n");

    int b[2][3][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,
                    14,15,16,17,18,19,20,21,22,23,24};
    printf("b=\n");
    for(i=0;i<2;i++)
        for(j=0;j<3;j++)
            for(k=0;k<4;k++)
                printf("%d\t",b[i][j][k]);
    printf("\n");

    printf("b=\n");
    for(i=0;i<2;i++){
        for(j=0;j<3;j++)
            printf("%p\t",b[i][j]);
        printf("\n");
    }
    return 0;
}
  • Generator in C
  • generate random integers in {0,1,...,99} uniformly
  • generate random double in interval [0,1] uniformly
// generate random numbers uniformly 
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
    int i, x[100];
    double a[100], b[4][25], c[25][4], seed = 1;

    srand(seed+1);
    for (i = 0; i < 100; i++)
        x[i] = rand();
    for (i = 0; i < 100; i++){
            if(!(i%10)) printf("\n");
            printf("%d\t",x[i]);
    }
    printf("\n");


    srand(seed);
    for (i = 0; i < 100; i++)
        a[i] = (rand()%100)/100.0;
        //a[i] = 1.0/(rand()%100);
    for (i = 0; i < 100; i++){
            if(!(i%10)) printf("\n");
            printf("%5.2f",a[i]);
    }
    printf("\n");

    srand(1);
    for (i = 0; i < 100; i++){
        b[i / 25][i % 25] = (rand() % 100) / 100.0;
    }
    for (i = 0; i < 100; i++){
        if(!(i%25)) printf("\n");
        printf("%5.2f",b[i / 25][i % 25]);
    }

    srand(1000);
    for (i = 0; i < 100; i++)
        c[i / 4][i % 4] = (rand() % 100) / 100.0;

    for (i = 0; i < 100; i++){
        if(!(i%4)) printf("\n");
        printf("%5.2f",c[i / 4][i % 4]);
    }
}

2 Sugar functions

2.1 Find the maximal element in a matrix, and print the corresponding row and column

  • store the data via a two-dimensional array
// find the maximal element in a matrix, and print the corresponding row and column.
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 4
#define M 25
int main(){
    int i, j, row=0, colum=0;
    double a[N][M], max;
    srand(1);
    for (i = 0; i < N*M; i++)
        a[i / M][i % M] = (rand() % 1000) / 100.0;

    max=a[0][0];
    for(i=0;i<N;i++)
        for(j=0;j<M;j++)
            if(a[i][j]>max){    
                max = a[i][j];
                row = i;
                colum = j;
            }
    printf("max=%lf\n(row, colum) = (%d, %d)\n",max,row,colum);
    return 0;
}
  • store the data via an one-dimensional array
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 4
#define M 25
int main(){
    int i, row=0, colum=0;
    double a[N*M], max;
    srand(1);
    for (i = 0; i < N*M; i++)
        a[i] = (rand() % 1000) / 100.0;

    max=a[0];
    for(i=0;i<N*M;i++)
        if(a[i]>max){
            max = a[i];
            row = i/M;
            colum = i%M;
        }
    printf("max=%lf\n(row, colum) = (%d, %d)\n",max,row,colum);
    return 0;
}

2.2 Transpose a matrix

  • store the data via a two-dimensional array
// Transpose a matrix
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 4
#define M 6
int main()
{
    int i,j,a[N][M],b[M][N];
    srand(1);
    for (i = 0; i < N*M; i++)
        a[i / M][i % M] = rand() % 100;
    printf("array a:\n");
    for(i=0;i<N;i++){
        for (j=0;j<M;j++){
            printf("%5d",a[i][j]);
            b[j][i]=a[i][j];
        }
        printf("\n");
    }
    printf("array b:\n");
    for(i=0;i<M;i++){
        for(j=0;j<N;j++){
            printf("%5d",b[i][j]);
        }
        printf("\n");
    }
}
  • store the data via an one-dimensional array
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 4
#define M 5
int main()
{
    int i,j,a[N*M],b[N*M];
    srand(1);
    for (i=0;i<N*M;i++)
        a[i] = rand() % 100;


    printf("array a:\n");
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            printf("%5d",a[i*M+j]);
            b[i+j*N] = a[i*M+j];
        }
        printf("\n");
    }

    printf("\n\narray b:\n");
    for(i=0;i<M;i++){
        for(j=0;j<N;j++)
            printf("%5d",b[i*N+j]);
        printf("\n");
    }
    return 0;
}
  • or
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 4
#define M 5
int main()
{
    int i,j,a[N*M],b[M*N];
    srand(1);
    for (i=0;i<N*M;i++)
        a[i] = rand() % 100;

    printf("array a:\n");
    for(i=0;i<N*M;i++){
        if(!(i%M)) printf("\n");
        printf("%5d",a[i]);
        b[(i%M)*N + i/M] = a[i];
    }
    
    printf("\n\narray b:\n");
    for(i=0;i<M*N;i++){
        if(!(i%N)) printf("\n");
        printf("%5d",b[i]);
    }
    return 0;
}

2.3 Calculate the square root

  • Calculate the square root of n acoording to the iteration formula
#include <stdio.h>
#include <math.h>
#define EPS 1e-5
int main()
{
    // Find the square root of a positive integer.
    float a,x0,x1;
    printf("enter a positive number:");
    scanf("%f",&a);
    x0=a/2;
    x1=(x0+a/x0)/2;
    do{
        x0=x1;
        x1=(x0+a/x0)/2;
    }while(fabs(x0-x1)>=EPS);
    printf("The square root of %5.2f  is %8.5f\n",a,x1);

    /*
    int step = 0;
    x0=a/2;
    while(step<100){
        step++;
        x1=(x0+a/x0)/2;
        if(fabs(x0-x1)<EPS) break;
        x0=x1;
    }
    printf("The square root of %5.2f  is %8.5f\n",a,x1);
    printf("It runs %d steps\n",step);
    */

    return 0;
}

2.4 One more example

  • find a minimal natural number n such that n/2 is a squared number, and n/3 is a cubed number
  • a naive method
#include <stdio.h>
#include <math.h>
int issquared(int n){
    int x = sqrt(1.0*n);
    if(x*x==n)  return 1;
    else return 0;
}

int iscubed(int n){
    int x = pow(1.0*n,1.0/3),x1 = x+1;
    if(x*x*x==n||x1*x1*x1==n) return 1;
    else return 0;
}
int main()
{
    int n=6,n2,n3;
    while(n<700){
        n2 = n/2;
        n3 = n/3;
        if(issquared(n2)&&iscubed(n3))
            break;
        n += 6;
    }
    printf("The lowest positive integer n is %d\n",n);
    return 0;
}
  • a better method
#include <stdio.h>
#include <math.h>
int issquared(int n){
    int x = sqrt(1.0*n);
    if(x*x==n)  return 1;
    else return 0;
}

int main()
{
    int n,n2,n3=2;
    while(n3<100){
        n = n3*n3*n3*3;
        n2 = n/2;
        if(issquared(n2))
            break;
        n3++;
    }
    printf("The lowest positive integer n is %d\n",n);
    return 0;
}

3 Problem in the previous week

1 Calculate 1/2019 with 100-digit precesion and save them in an array (int or char). Print it with 10 digits per line.

#include <stdio.h>
int fraction(int b[], int n, int c){
    // calculate 1/2019 with 100-digit precesion
    int a=1,cnt=0;
    while(cnt<=n)
    {
        if(a<c)
        while(1){
            b[cnt++]=0;
            a=a*10;
            if(a>=c) break;
        }
        b[cnt]=(int)(a/c);
        a=(a%c)*10;
        cnt++;
    }
    printf("0.");
    for(cnt=1;cnt<=n;cnt++) printf("%d",b[cnt]);
    printf("\n");
    return 1;
}

int main(){
    // calculate 1/2019 with 100-digit precesion
    int i,a[110]={0},ans[110]={0},b=2019;
    a[0]=1;
    printf("One result is \n");
    for(i=0;i<=100;i++){
        a[i+1]+=(a[i]%b)*10;
        ans[i]=a[i]/b;
        printf("%d",ans[i]);
        if(i==0) printf(".");
    }
    printf("\n");
    printf("Another result is \n");
    fraction(a, 100, b);
    return 0;
}

2 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

  • More generally, what is the smallest positive number that is evenly divisible by all of the numbers from 1 to N? Here N could be large, such as 10000.
#include<stdio.h>
#include<math.h>
#define N 40
int isPrime(int n){
    int i=2;
    double sqrtn=sqrt(1.0*n);
    while(i<=sqrtn){
        if(!(n%i)) return 0;
        i++;
    }
    return 1;
}

int product(int curr_len, int n, int fact[], int digits){
    int i,temp1=0;
    curr_len+=digits-1;
    for(i=0;i<curr_len;i++){
        temp1=fact[i]*n+temp1/10;
        fact[i]=temp1%10;
    }
    if(temp1/10){ fact[i]=temp1/10;curr_len++;}
    return curr_len;
}

int isDivededBy1toN(int fact[],int n){
    int i=2,j,count=0,m0,a[20];
    int curr_len=1,digits,m;

    for(i=2;i<=n;i++)
        if(isPrime(i)) a[count++]=i;
    for(j=0;j<count;j++){
        m0=i=a[j];
        while((i*=a[j])<=n) m0 = i;
        digits = 1;
        m=m0;
        while(m/10){
            digits++;
            m/=10;
        }
        curr_len = product(curr_len,m0,fact,digits);
        printf("i=%d\n",m0);
    }
    return curr_len;
}

int main(){
    int i,fact[100],curr_len;
    for(i=0;i<100;i++) fact[i]=0;
    fact[0]=1;
    curr_len = isDivededBy1toN(fact,N);

    for(i=curr_len-1;i>=0;i--) printf("%d",fact[i]);

    return 0;
}

4 Problems