11.7 Tutorial4

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

Introduction to Computer Science

Tutorial 4: iteration and problem solving

1. Manual Execution

Manually execute the following programs.

for (int var = begin; var < end; var += step) {
    // loop body
}

Program 1.1

int i = 1;
int a = 2;
for(i = 3; i <= 5; i += 2)
    a *= a;

Initial values: i = 1, a = 2.
Loop Execution:
- Set i = 3 at the beginning of the for loop.
- First iteration (i = 3):
- a = a * a = 2 * 2 = 4
- i += 2, so i = 5.
- Second iteration (i = 5):
- a = a * a = 4 * 4 = 16
- i += 2, so i = 7, which exits the loop.
Final values: a = 16, i = 7.

Program 1.2

int i = 5;
int a = 0;
int b = 0;
for(i = 0; i <= 2; a++, i++)
    b = a + i;

Initial values: i = 5, a = 0, b = 0.
Loop Execution:
- Set i = 0 at the beginning of the for loop.
- First iteration (i = 0, a = 0):
- b = a + i = 0 + 0 = 0
- a++ (post-increment), so a = 1
- i++, so i = 1
- Second iteration (i = 1, a = 1):
- b = a + i = 1 + 1 = 2
- a++, so a = 2
- i++, so i = 2
- Third iteration (i = 2, a = 2):
- b = a + i = 2 + 2 = 4
- a++, so a = 3
- i++, so i = 3, which exits the loop.
Final values: a = 3, b = 4, i = 3.

Program 1.3

int i = 3;
int a = 2;
int b = 3;
i /= 5;
if (i)
    a = b;
else
    b = a;
a = (i += b, ++b);

Initial values: i = 3, a = 2, b = 3.
Execution:
- i /= 5 results in i = 3 / 5 = 0 (integer division).
- if (i): Since i = 0, the condition is false, so the else block executes.
- b = a, so b = 2.
- a = (i += b, ++b);
- i += b results in i = 0 + 2 = 2.
- ++b increments b to 3.
- a = 3 (the final result of the comma expression).
Final values: a = 3, b = 3, i = 2.

2. Programs output

What is the output of these programs?

Program 2.1

int i, j;
for(i = 0; i < 3; i++)
    for(j = i + 1; j < 3; j++)
        printf("%d %d\n", i, j);

Loop Execution:
- When i = 0:
- j = i + 1 = 1
- Since j < 3, it enters the inner loop and prints 0 1.
- j++, so j = 2
- Since j < 3, it continues in the inner loop and prints 0 2.
- j++, so j = 3, which exits the inner loop.
- When i = 1:
- j = i + 1 = 2
- Since j < 3, it enters the inner loop and prints 1 2.
- j++, so j = 3, which exits the inner loop.
- **When i = 2**:
- j = i + 1 = 3, which does not satisfy j < 3, so the inner loop does not execute.
Output for Program 2.1:
```
0 1
0 2
1 2
```

Program 2.2

int i, j, a;
for(a = 0, i = 0; i <= 5; i++)
    for(j = 0; j <= 5; j++)
        a++;
printf("%d %d %d\n", a, i, j);

Loop Execution:
- The outer loop runs with i ranging from 0 to 5, so it iterates 6 times.
- The inner loop runs with j ranging from 0 to 5, so it iterates 6 times for each value of i.
- Each time the inner loop runs, a++ increments a by 1.
- Since the inner loop runs 6 times for each of the 6 iterations of the outer loop, a increments a total of 6 * 6 = 36 times.
Final values:
- a = 36 (after all increments)
- i = 6 (after the outer loop finishes)
- j = 6 (after the inner loop finishes on the last iteration)
Output for Program 2.2:
```
36 6 6
```

3. Problem Solving

For each of the following problems, write a C program to solve it.

3.1

Find all the divisors of a given positive number x, where x is received by standard input (using scanf).

#include <stdio.h>

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

3.2

Find all pairs (x, y) of coprime numbers, where x, y are smaller than 1000.

#include <stdio.h>

int main() {
    for (int x = 1; x < 1000; x++) {
        for (int y = x; y < 1000; y++) { //let y = x to avoid repeat
            int flag = 1;// suppose they are comprime at first
            for (int divisor = 2; divisor <= y && divisor <= x; divisor++ ) {
                if ((x % divisor == 0) && (y % divisor == 0)) {
                    flag = 0;
                    break;
                }
            }

            if (flag == 1){
                printf(" (%d %d) ", x ,y);
            }
        }
    }
    return 0;
}

3.3

Find two natural numbers a < b such that a^2 = 2 * b and a + b = 1012. Print their values.

#include <stdio.h>

int main() {
    for (int a = 1; a < 1012; a++) {  // Limit a to 1012
        for (int b = a; b < 1012; b++) {  // Limit b to 1012
            if ((a * a == 2 * b) && (a + b == 1012)) {
                printf("(a = %d, b = %d)\n", a, b);
                return 0;
            }
        }
    }
    return 0;
}

3.4

Given a natural number n (received from the user from standard input), compute and print out the product 1 * 2 * … * n (factorial of n).

#include <stdio.h>

int main() {
    int n, number = 1;
    scanf("%d", &n);
    for (; n!=0; n--) {
        number = number*n;
        }
    printf("%d", number);
    return 0;
}

3.5

A Pythagorean triplet is a set of three natural numbers for which a^2 + b^2 = c^2. For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. Write a program that given a positive number n provided by the user, prints out all Pythagorean triplets where a, b, and c are smaller than n.

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    for (int a = 1; a < n; a++) {
        for (int b = a; b < n; b++) {
            for (int c = b; c < n; c++) {
                if (a * a + b * b == c * c) {
                    printf("%d*%d+%d*%d=%d*%d\n", a, a, b, b, c, c);
                }
            }
        }
    }
    return 0;
}

3.6

Modify the Pythagorean triplet program so that the program terminates as soon as it finds the first Pythagorean triplet.

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    for (int a = 1; a < n; a++) {
        for (int b = a; b < n; b++) {
            for (int c = b; c < n; c++) {
                if (a * a + b * b == c * c) {
                    printf("%d*%d+%d*%d=%d*%d\n", a, a, b, b, c, c);
                    return 0;
                }
            }
        }
    }
    return 0;
}

‍