Skip to content

12.11 Tutorial 9

intro-to-computer-science-gtiit-tutorial-09-2024.pdf

Introduction to Computer ScienceTutorial 9: Functions

  1. Some Arithmetic Functions
    In a C file, define the following functions:

    1. ​int square(int)​ that calculates the mathematical function \(x \to x^2\).
    2. ​int abs(int)​ that calculates the function \(x \to \{-x \text{ if } x < 0, x \text{ otherwise} \}\).
    3. ​int max(int, int)​ that calculates the function \((x, y) \to \{x \text{ if } x > y, y \text{ otherwise} \}\).
    4. ​int maxAbs(int, int)​ that calculates the function \((x, y) \to \{|x| \text{ if } |x| > |y|, |y| \text{ otherwise}\}\).
      The definition of maxAbs​ should not use any conditional statement or operator, and should call the previous functions abs​ and max​.

    Write a main​ function that allows you to test your functions.

    #include<stdio.h>

int square(int x) {
    return x*x;
}

int abs(int x) {
    if(x < 0)
        return -x;
    else 
        return x;
}

int max(int x, int y) {
    if(x > y)
        return x;
    else
        return y;
}

int maxAbs(int x, int y) {
    return max(abs(x),abs(y));
}

int main() {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("The square result is %d, %d\n", square(x), square(y));
    printf("The abs result is %d, %d\n", abs(x), abs(y));
    printf("The max result is %d\n", max(x, y));
    printf("The maxAbs result is %d\n", maxAbs(x, y));
}

  2. Prime Numbers and Fibonacci Numbers
    2.1 Define a function int isPrime(int n)​ that returns 1 if \(n\) is a prime number and 0 otherwise.
    Write a main​ function that reads an integer from standard input and checks whether it is a prime number, showing the result of the check on standard output.

    #include <stdio.h>

int isPrime(int n) {
    if(n <= 1)
        return 0;
    else if(n == 2)
        return 1;
    else {
        for(int i = 2; i < n; i++) {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", isPrime(n));
    return 0;
}

    2.2 Write a function int fibonacci(int n)​ that returns the \(n\)-th Fibonacci number.
    Write a main​ function that reads an integer \(n\) from standard input and prints out the \(n\)-th Fibonacci number on standard output.

    #include <stdio.h>

int fibonacci(int n) {
    if(n == 0)
        return 0;
    if (n == 1) 
        return 1;
    else 
        return fibonacci(n - 1) + fibonacci(n - 2);
}

/*
int fibonacci_2(int n) {
    int aux_1 = 0;
    int aux_2 = 1;
    for (int i = 0; i < n - 1; i++) {
        if(i % 2 == 0) {
            aux_1 += aux_2;
        } else {
            aux_2 += aux_1;
        }
    }
    if(n % 2 == 0) {
        return aux_1;
    } else {
        return aux_2;
    }
}
*/

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", fibonacci(n));
}

    2.3 Write a program that reads an integer \(n\) from standard input (or, better, as a command line argument) and finds the positive integers smaller or equal to \(n\) that are at the same time Fibonacci numbers and prime numbers.

    What is int main(int argc, char* argv[])​?

    For example, if we input ./a.out word1 word2 word3​

    Then we will have argc = 4​ and an array argv which is "./a.out" "word1" "word2" "word3"​

    #include <stdio.h>
//include <stdlib.h>

int fibonacci(int n) {
    if(n == 0)
        return 0;
    if (n == 1) 
        return 1;
    else 
        return fibonacci(n - 1) + fibonacci(n - 2);
}

/*
int fibonacci_2(int n) {
    int aux_1 = 0;
    int aux_2 = 1;
    for (int i = 0; i < n - 1; i++) {
        if(i % 2 == 0) {
            aux_1 += aux_2;
        } else {
            aux_2 += aux_1;
        }
    }
    if(n % 2 == 0) {
        return aux_1;
    } else {
        return aux_2;
    }
}
*/

int isPrime(int n) {
    if(n <= 1)
        return 0;
    else if(n == 2)
        return 1;
    else {
        for(int i = 2; i < n; i++) {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
}

int isFibonacci(int n) {
    for(int i = 1; fibonacci(i) <= n; i++) {
        if(n == fibonacci(i))
            return 1;
    }
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        if(isFibonacci(i) == 1 && isPrime(i) == 1)
            printf("%d\n", i);
    } 
    return 0;
}

/*
int main(int argc, char* argv[]) {
    int n = atoi(argv[1]);//convert string to number, such as "33" to 33
     for(int i = 1; i <= n; i++) {
        if(isFibonacci(i) == 1 && isPrime(i) == 1)
            printf("%d\n", i);
    } 
    return 0;
}
*/

  3. Goldbach Conjecture
    The Goldbach conjecture says that every even integer \(n\) greater than 2 is the sum of two prime numbers.
    Computers have been used extensively to test this conjecture. No counterexample has ever been found.
    Write a C program that will test the conjecture for all even integers between \(n\) and \(m\), positive integers received from standard input.
    Your output must show, for each even integer, if decomposable as two primes, the two that lead to the number. For instance:

    700 = 17 + 683  702 = 11 + 691

    #include<stdio.h>

int isPrime(int n) {
    if(n <= 1)
        return 0;
    else if(n == 2)
        return 1;
    else {
        for(int i = 2; i < n; i++) {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = n; i <= m; i++) { //generate the number between n and m
        for(int j = 2; j < i; j++) { //generate the decompose part
            if(isPrime(j) == 1) { //use j prime number as one part
                if(isPrime(i - j) == 1) { //if the substraction is prime, then satisfying
                    printf("%d = %d + %d\n", i, j, i-j );
                }
            }
        }
    }

    return 0;
}

    #include<stdio.h>
#include<stdlib.h>

int isPrime(int n) {
    if(n <= 1)
        return 0;
    else if(n == 2)
        return 1;
    else {
        for(int i = 2; i < n; i++) {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
}

//*first means: get the value in that address, then we can change the parameter
int canDecompose(int n, int *first, int *second) { 
    *first = n - 1;
    *second = 1;
    while ((!isPrime(*first) || !isPrime(*second)) && *first > 0) {
        (*first)--;
        (*second)++;
    }
    if (isPrime(*first) && isPrime(*second)) 
        return 1;
    else 
        return 0;

}

void golbach(int n) {//return nothing
    int first_component;
    int second_component;
    if(canDecompose(n, &first_component, &second_component)) { //pass address insted of value 
        printf("%d + %d = %d\n", first_component, second_component, n);
    }
    else
        printf("Counterexample\n!");
}

int main(int argc, char* argv[]) {
    int bound = atoi(argv[1]);
    for(int i = 2; i < bound; i+=2) {
        golbach(i);
    }
    return 0;
}

    #include<stdio.h>
#include<stdlib.h>

int isPrime(int n) {
    if(n <= 1)
        return 0;
    else if(n == 2)
        return 1;
    else {
        for(int i = 2; i < n; i++) {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
}

//*first means: get the value in that address, then we can change the parameter

void canDecompose(int n) {
    int first = n-1;
    int second = 1;
    while((!isPrime(first) || !isPrime(second)) && (first > 0)) {
        (first)--;
        (second)++;
    }
    if(isPrime(first) && isPrime(second)) {
        printf("%d + %d = %d\n", first, second, n);
    } else {
        printf("Counterexample\n");
    }
}

int main(int argc, char* argv[]) {
    int bound = atoi(argv[1]);
    for(int i = 2; i < bound; i+=2) {
        canDecompose(i);
    }
    return 0;
}

    another better way?

  4. Strings
    4.1 Design and implement in C a program that receives two strings from standard input (or from the command line, would be better) and decides whether these strings are anagrams.

    #include<stdio.h>
#define maxinput 32

int main() {
    int ch;
    int sequence1[maxinput];
    int digits1 = 0;

    // Read the first string
    ch = getchar();
    while(ch != '\n') {  // Keep reading characters until newline
        sequence1[digits1] = ch;
        ch = getchar();
        digits1++;
    }

    int sequence2[maxinput];
    int digits2 = 0;

    // Read the second string
    ch = getchar();
    while(ch != '\n') {  // Keep reading characters until newline
        sequence2[digits2] = ch;
        ch = getchar();
        digits2++;
    }

    // Check if the lengths of both strings are different
    if(digits1 != digits2) {
        printf("No!");  // Strings cannot be anagrams if their lengths are different
    } 
    else {
        int isSame;
        // Compare characters from both sequences
        for(int i = 0; i < digits1; i++) {
            isSame = 0;
            for(int j = 0; j < digits1; j++) {
                if(sequence1[i] == sequence2[j] && isSame == 0) {
                    sequence1[i] = 0;  // Mark this character as matched
                    sequence2[j] = 0;  // Mark this character as matched
                    isSame = 1;  // Avoid re-matching this character
                }
            }
        }
        int notzero = 0;
        // Check if any characters are left unmatched (non-zero)
        for(int k = 0; k < digits1; k++) {
            if(sequence1[k] != 0) {
                notzero = 1;  // Found an unmatched character
            }
        }

        // If no unmatched characters, the strings are anagrams
        if(notzero == 0)
            printf("yes");
        else
            printf("no");
    }
    return 0;
}

    #include<stdio.h>
#define maxinput 100

// Function to read a string sequence from input
int readSequence(int sequence[]) {
    int ch;
    int digits = 0;
    ch = getchar();
    while(ch != '\n') {  // Read characters until newline
        sequence[digits] = ch;
        ch = getchar();
        digits++;
    }
    return digits;
}

// Function to compare two sequences and mark matched characters
void compareSequences(int sequence1[], int sequence2[], int length) {
    for(int i = 0; i < length; i++) {
        int isSame = 0;
        for(int j = 0; j < length; j++) {
            // If characters match and have not been matched before
            if(sequence1[i] == sequence2[j] && isSame == 0) {
                sequence1[i] = 0;  // Mark this character as matched
                sequence2[j] = 0;  // Mark this character as matched
                isSame = 1;  // Prevent re-matching the same character
            }
        }
    }
}

// Function to check if there are any unmatched characters
int checkResult(int sequence[], int length) {
    for(int k = 0; k < length; k++) {
        if(sequence[k] != 0) {
            return 1;  // Return 1 if there is a non-zero (unmatched) character
        }
    }
    return 0;  // All characters are matched, return 0
}

int main() {
    int sequence1[maxinput];
    int sequence2[maxinput];

    // Read two sequences (strings) from input
    int digits1 = readSequence(sequence1);
    int digits2 = readSequence(sequence2);

    // Check if the lengths of the strings are equal
    if(digits1 != digits2) {
        printf("No!");  // Strings cannot be anagrams if their lengths differ
        return 0;
    }

    // Compare the two sequences to check for anagram
    compareSequences(sequence1, sequence2, digits1);

    // Check if the sequences are fully matched and output the result
    if(checkResult(sequence1, digits1) == 0) {
        printf("yes");  // Strings are anagrams
    } else {
        printf("no");   // Strings are not anagrams
    }

    return 0;
}

‍