Skip to content

12.27 Lab11

introduction-to-computer-science-laboratory-11.pdf

Introduction to Computer Science - Laboratory 11

Exercises

  1. Remove Duplicates from an Array Design and implement a C program that, given an integer sequence represented as an array, removes all the repeated elements in the sequence.

    #include <stdio.h>

//read the sequence use scanf
int read(int seq[]) {
    int curr_number;
    int i = 0;
    while((scanf("%d", &curr_number)) == 1) {
        seq[i] = curr_number;
        i++;
    }
    return i;
}

//gengerate a new sequence from the origin one without repeated number
int remov(int seq[], int origin[], int digit) {
    int position = 0;
    int is_repeat;
    for(int i = 0; i < digit; i++) { //fix the i-th number in origin
        is_repeat = 0;
        for(int j = 0; j < position; j++) { 
        //check i-th number in origin whether it is repeat
            if(origin[i] == seq[j])
                is_repeat = 1;
        }
        if(is_repeat == 0) {
                seq[position] = origin[i];
                position++;
            }
    }
    return position;
}

// print sequence
void print(int seq[], int digit) {
    for(int i = 0; i < digit; i++) {
        printf("%d\n", seq[i]);
    }
}

int main() {
    int original_seq[2048];
    int digit = read(original_seq);
    int outcome_seq[digit];
    int digit2 = remov(outcome_seq, original_seq, digit);
    print(outcome_seq, digit2);
}

  2. Longest Ordered Subsequence Develop a C program that takes as input an integer sequence s​ and calculates the longest ordered subsequence in s​. Example: If s = 1, 2, 3, 4, 3, 2, 1, 0​, the result should be 4, 3, 2, 1, 0​

    #include<stdio.h>

//read the sequence use scanf
int read(int seq[]) {
    int curr_number;
    int i = 0;
    while((scanf("%d", &curr_number)) == 1) {
        seq[i] = curr_number;
        i++;
    }
    return i;
}

//given a start_position of sequence, we calculate the length of ordered sequence
int calculate_length(int seq[], int start_position, int size) {
    int monotone = -1; //indicate 1==increasing or 0==decreasing, -1 is unknown
    int position = start_position;// position is to find the monotone status
    while(monotone == -1) {
        if(seq[position + 1] > seq[position]) 
            monotone = 1;
        else if(seq[position + 1] < seq[position])
            monotone = 0;
        else
            position++;
    }
    int length = 1;
    if(monotone == 1) {
        int i;
        for(i = start_position; i + 1 < size && seq[i+1] >= seq[i]; i++) {
            length++;
        }
    }
    else {
        int i;
        for(i = start_position; i + 1 < size && seq[i+1] <= seq[i]; i++) {
            length++;
        }
    }
    return length;
}

//calculate the length of order sequence from 0 to size -1, then take the max
int max_length(int seq[], int size, int* start_position) {
    int max = 1;
    for(int i = 0; i < size; i++) {
        if(calculate_length(seq, i, size) > max) {
            max = calculate_length(seq, i, size);
            *start_position = i;
        }
    }
    return max;
}

//printf sequence
void print(int seq[], int length, int start_position) {
    for(int i = start_position; i < start_position + length; i++) 
            printf("%d,",seq[i]);
}

int main() {
    int seq[2048];
    int size = read(seq);
    int start_position = 0;
    int length = max_length(seq, size, &start_position);
    print(seq, length, start_position);
    return 0;
}

  3. Cumulative Sum Write a C program that calculates the cumulative sum for an integer sequence taken as a parameter. Example: If the sequence is 1, 5, -2, 7​, the result should be 1, 6, 4, 11​.

    #include<stdio.h>

//read the sequence use scanf
int read(int seq[]) {
    int curr_number;
    int i = 0;
    while((scanf("%d", &curr_number)) == 1) {
        seq[i] = curr_number;
        i++;
    }
    return i;
}

//calculate the cumulative number in position i
int cumulative_number(int seq[], int position) {
    if(position == 0) 
        return seq[position];
    else 
        return cumulative_number(seq, position - 1) + seq[position];
}

void print(int seq[], int size) {
    for(int i = 0; i < size; i++) {
        printf("%d,",cumulative_number(seq, i));
    }

}

int main() {
    int seq[2048];
    int size = read(seq);
    print(seq, size);
    return 0;
}

  4. Count Character Occurrences Without using arrays, develop a program that takes as input a string str​ and a character c​. Then counts how many times c​ appears in str​.

    #include<stdio.h>

//calculate the length of string
int length(char str[]) {
    int i;
    for(i = 0; str[i] != '\0'; i++) {}
    return i - 1;
}

//calculate the times of c occuring
int times(char str[], char c, int length) {
    int times = 0;
    for(int i = 0; i < length; i++) {
        if(str[i] == c)
            times++;
    }
    return times;
}

int main() {
    char str[1000];
    fgets(str, 1000, stdin);
    int len = length(str);
    char c;
    printf("character?");
    scanf("%c", &c);
    printf("%d",times(str, c, len));
    return 0;
}

  5. Pattern Matching in Text Write a C program that takes two strings as input (text​ and pattern​) and decides if there is at least one occurrence of the pattern in the text.

    #include<stdio.h>

//calculate the length of string
int length(char str[]) {
    int i;
    for(i = 0; str[i] != '\0'; i++) {}
    return i - 1;
}

//calculate the times of c occuring
int is_occur(char str1[], char str2[], int length1, int length2) {
    int is_same;
    int position;//the position of array pattern
    for(int i = 0; i <= length1 - length2; i++) {
        //search from 0 to the last possible first character
        is_same = 1;
        if(str2[0] == str1[i]) { //find the first character
            position = 1;
            for(int k = i + 1; k < i + length2; k++) { //check the remaining
                if(str2[position] != str1[k])
                    is_same = 0;
                position++;
            }
            if(is_same) 
                return 1;
        }
    }
    return 0;
}

int main() {
    char str_text[1000];
    fgets(str_text, 1000, stdin);
    int len_text = length(str_text);

    char str_pattern[1000];
    fgets(str_pattern, 1000, stdin);
    int len_pattern = length(str_pattern);

    printf("%d", is_occur(str_text, str_pattern, len_text, len_pattern));
    return 0;
}

  6. Lexicographical Order Check Design and implement a C program that, given a string, decides if it is in lexicographical order. Example: "Art"​ is in lexicographical order, but "Hello"​ is not.

    #include<stdio.h>

//calculate the length of string
int length(char str[]) {
    int i;
    for(i = 0; str[i] != '\0'; i++) {}
    return i - 1;
}

//examine where it is lexicographical
int is_lexicographical(char str[], int length) {
    int is_lexico = 1;
    for(int i = 0; i + 1 < length; i++) {
        if(str[i + 1] < str[i])
            is_lexico = 0;
    }
    return is_lexico;
}

int main() {
    char str[1000];
    fgets(str, 1000, stdin);
    int len = length(str);

    printf("%d", is_lexicographical(str, len));
    return 0;
}

  7. Recursive and Iterative Solutions

    • If you resolved exercises 2 and 4 without using recursion, find a recursive solution for them.
    • Otherwise, find an iterative solution for them.
#include<stdio.h>

// Read the sequence using scanf
int read_sequence(int seq[]) {
    int curr_number;
    int i = 0;
    while((scanf("%d", &curr_number)) == 1) {
        seq[i] = curr_number;
        i++;
    }
    return i;
}

// Recursive function to determine monotone direction
int determine_monotone(int seq[], int position, int size) {
    if (position + 1 >= size) return -1; // No direction found
    if(seq[position + 1] > seq[position]) 
        return 1;
    else if(seq[position + 1] < seq[position])
        return 0;
    else
        return determine_monotone(seq, position + 1, size);
}

// Recursive function to calculate the length of ordered sequence
int calculate_length_recursive(int seq[], int start_position, int size, int monotone) {
    if(start_position + 1 >= size) 
        return 1;
    if(monotone == 1 && seq[start_position + 1] >= seq[start_position])
        return 1 + calculate_length_recursive(seq, start_position + 1, size, monotone);
    if(monotone == 0 && seq[start_position + 1] <= seq[start_position])
        return 1 + calculate_length_recursive(seq, start_position + 1, size, monotone);
    return 1;
}

// Recursive function to find the maximum length and its start position
int max_length_recursive(int seq[], int size, int current, int max, int *start_position) {
    if(current >= size)
        return max;

    // Determine monotone direction starting from current
    int monotone = determine_monotone(seq, current, size);
    if(monotone == -1) {
        // No direction found, single element
        if(1 > max) {
            max = 1;
            *start_position = current;
        }
    } else {
        // Calculate length based on monotone
        int length = calculate_length_recursive(seq, current, size, monotone);
        if(length > max) {
            max = length;
            *start_position = current;
        }
    }
    return max_length_recursive(seq, size, current + 1, max, start_position);
}

// Recursive function to print the subsequence
void print_recursive(int seq[], int length, int start_position) {
    if(length <= 0)
        return;
    printf("%d", seq[start_position]);
    if(length > 1)
        printf(", ");
    print_recursive(seq, length - 1, start_position + 1);
}

int main() {
    int seq[2048];
    int size = read_sequence(seq);
    int start_position = 0;
    int length = max_length_recursive(seq, size, 0, 1, &start_position);
    print_recursive(seq, length, start_position);
    printf("\n");
    return 0;
}

#include<stdio.h>

// Recursive function to calculate the length of the string
int length_recursive(char str[]) {
    if(str[0] == '\0')
        return 0;
    return 1 + length_recursive(str + 1);
}

// Recursive function to count occurrences of character c
int times_recursive(char str[], char c) {
    if(str[0] == '\0')
        return 0;
    if(str[0] == c)
        return 1 + times_recursive(str + 1, c);
    else
        return times_recursive(str + 1, c);
}

int main() {
    char str[1000];
    fgets(str, 1000, stdin);
    int len = length_recursive(str);
    char c;
    printf("character? ");
    scanf(" %c", &c); // Added space before %c to consume any leftover newline
    printf("%d\n", times_recursive(str, c));
    return 0;
}

‍