1. Fibonacci
The Fibonacci-series is defined as: F0=0, F1=1, Fn=Fn-1+Fn-2, thus the next element of the series is the sum of the previous two. The first couple of elements are 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Write a program that calculates the nth element of the series, where n is given by the user.
Solution
Let us introduce two variables representing the previous two elements of the series Fn-1 and Fn-2 (called f1 and f2 in the solution below).
In each iteration of the loop, we "slide" this window, thus we assign Fn-1 to Fn-2, Fn to Fn-1, and
calculate the next element of the series as Fn-1+Fn-2. It is important to note that the order of assignments matters, f2 = f1;
f1 = f; and f1 = f; f2 = f1; gives different result. Why?.
#include <stdio.h>
int main() {
int f = 1, f1 = 1, f2 = 0, i, n;
scanf("%d", &n);
if (n > 0) {
for (i = 2; i < n; i = i + 1) {
f2 = f1;
f1 = f;
f = f1 + f2;
}
printf("%d\n", f);
}
else if (n == 0) {
printf("0\n");
}
else {
printf("Invalid input, non-negative integer needed.\n");
}
return 0;
}
2. Square root of number 2
The digits of √2 can be generated iteratively step-by-step, with an elegant algorithm. First observe that the square root must be between 1 and 2. The former is too small, the latter is too big to be the square root since 12=1 és 22=4. Along this reasoning let us determine the first digit after the decimal point:
| Number | Its square |
|---|---|
| 1.0 | 1.00 – too small |
| 1.1 | 1.21 – too small |
| 1.2 | 1.44 – too small |
| 1.3 | 1.69 – too small |
| 1.4 | 1.96 – too small |
| 1.5 | 2.25 – too big |
Consequently, the square root begins with 1.4. For the next digit:
| Number | Its square |
|---|---|
| 1.40 | 1.9600 – too small |
| 1.41 | 1.9881 – too small |
| 1.42 | 2.0164 – too big |
Thus, the result begins with 1.41. The task is to generalize this algrithm and to write a C program that prints the first 10 digits of √2.
Solution
#include <stdio.h>
int main()
{
double guess = 1;
double delta = 0.1;
for (int i = 1; i <= 10; i = i+1) {
while (guess*guess < 2) {
guess = guess + delta;
}
guess = guess - delta; /* why? */
delta = delta / 10;
}
printf("%.10f", guess);
return 0;
}
The greatest common divisor of two numbers a and b can be computed by the Euclidean algorithm. This is a very simple iterative algorithm.
In every iteration the greater one among a and b is selected, and the smaller one is substracted from it. This elementary step
is repeated as long as the two numbers are not equal. When they are equal, the number we get is the greatest common divisor. Implement the Euclidean algorithm in C!
Solution
#include <stdio.h>
int main() {
int a, b;
printf("Enter the two numbers: ");
scanf("%d %d", &a, &b);
while (a != b) {
if (a > b) {
a = a - b;
}
else {
b = b - a;
}
}
printf("The greatest common divisor is: %d\n", a); /* we could have printed b, too, they are equal */
return 0;
}
Write a program that asks the user to enter an integer number and prints the sum of the digits. E.g., if the user enters 123456, the program
prints 21 (=1+2+3+4+5+6).
Hint: The operator % in the C programming language represents the reminder of an integer division. For example, n%10
returns the remainder when variable n is divided by 10. Observe that this remainder is exactly the last digit of n.
Solution
As mentionied above, n%10 provides the last digit of the number. Ok, but how to obtain the next digit? Easily: let us get rid of the last digit
with the divison n/10! Now we can again check the last digit with the % operator (add it to the sum), get rid of the last digit again,
check it, etc.
#include <stdio.h>
int main() {
int number, sum = 0;
printf("Enter a number: ");
scanf("%d", &number);
while (number > 0) {
sum = sum + (number % 10);
number = number / 10;
}
printf("The sum of the digits is %d\n", sum);
return 0;
}
Palindromic numbers are "symmetric" numbers, they remain the same when their digits are reversed. For instance, 121 is a palindromic number, 123 is not. Write a C program that asks the user to enter an integer number and tests whether the number is palindromic or not. Do not use arrays.
Hint: We can already check the last digit by n%10, and we can transform any digit to the last position by
dividing it by the appropriate power of 10. With these two elementary steps check the digits at the appropriate positions by a loop.
Solution
The idea is to create a variable left, that, by dividing the number with it, transforms the currently checked left digit to the last position.
Similarly, dividing the number by variable right transforms the currently checked right digit to the last position. For example, if the user enters
12321, left=10000 initially, since (12321/10000) % 10 provides the leftmost digit. The initial value of right=1 makes it possible to extract
the rightmost digit by (12321/1) % 10. Since these two digits are equal, we can move on and check the next positions, variable left is divided by 10, while
right is multiplied by 10. This way the next comparison will involve (12321/1000) % 10, which is the second digit from the left, and (12321/10) % 10, which is
the second digit from the right. Again, variable left is divided by 10, while right is multiplied by 10, digits are compared, etc.
#include <stdio.h>
int main() {
int number, left = 1, right = 1, palindrom = 1;
printf("Enter a number: ");
scanf("%d", &number);
while (number / left > 0) {
left = left * 10;
}
left = left / 10;
while (left > right) {
if ((number/left)%10 != (number/right)%10) {
palindrom = 0; /* can not be palindromic any more */
break; /* ... so it makes no sense to contine */
}
left = left / 10;
right = right * 10;
}
if (palindrom == 1) {
printf("The number %d is palindromic.\n", number);
}
else {
printf("The number %d is not palindromic.\n", number);
}
return 0;
}