Problem Set 1-a Solutions
Problem 1. There is a 5-digit number that satisfies 4*abcde = edcba, that is, when multiplied by 4 yields
the same number read backwards. Write a C-program to find this number.
Solution:
#include
#define MIN 10000
#define MAX 24999 // solution has to be <25000
int main(void) {
int a, b, c, d, e, n;
for (n = MIN; n <= MAX; n++) {
a = (n / 10000) % 10;
b = (n / 1000) % 10;
c = (n / 100) % 10;
d = (n / 10) % 10;
e = n % 10;
if (4*n == 10000*e + 1000*d + 100*c + 10*b + a) {
printf("%d\n", n);
}
}
return 0;
}
Problem 2. Write a C program to compute the matrix product of two matrices A and B.
Solution:
#include
#define M 4
#define N 4
#define P 4
// Function matrixProduct computes a[][]*b[][], and stores the result in c[][]
void matrixProduct(float a[M][N], float b[N][P], float c[M][P]) {
int i, j, k;
for (i = 0; i < M; i++) {
for (j = 0; j < P; j++) {
c[i][j] = 0.0;
for (k = 0; k < N; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
}
int main()
{
float a[M][N] = { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}};
float b[N][P] = { {1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}};
float c[M][P]; // To store result
int i, j;
matrixProduct(a, b, c);
printf("Result matrix is \n");
for (i = 0; i < M; i++)
{
for (j = 0; j < P; j++)
printf("%f ", c[i][j]);
printf("\n");
}
return 0;
}
Problem 3. Write a C program that outputs, in alphabetical order, all the distinct strings that use each of
the characters 'c', 'a', 't', 'd', 'o', 'g' exactly once. How many strings does the program generate?
Solution:
#include
int main(void) {
char catdog[] = { ‘a’,’c’,’d’,’g’,’o’,’t’ };
int count = 0;
int i, j, k, l, m, n;
for (i=0; i<6; i++)
for (j=0; j<6; j++)
for (k=0; k<6; k++)
for (l=0; l<6; l++)
for (m=0; m<6; m++)
for (n=0; n<6; n++)
if (i!=j && i!=k && i!=l && i!=m && i!=n &&
j!=k && j!=l && j!=m && j!=n &&
k!=l && k!=m && k!=n &&
l!=m && l!=n && m!=n) {
printf("%c%c%c%c%c%c\n", catdog[i], catdog[j],
catdog[k], catdog[l],
catdog[m], catdog[n]);
count++;
}
printf("%d\n", count);
return 0;
}
Problem 4. Write a C function that takes a positive integer n as argument and outputs a series of
numbers according to the following process, until 1 is reached:
• If n is even, set n to n/2
• If n is odd, set n to 3*n+1
Solution:
void collatz(int n) { // named after the German mathematician who invented this problem
printf("%d\n", n);
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = 3*n + 1;
}
printf("%d\n", n);
}
}
Problem 5. Define a data structure to store all information of a single ride with the Opal card. Here are
two sample records:
You may assume that individual stops (such as "Anzac Pde D opp UNSW") require no more than 31
characters.
Determine the memory requirements of your data structure, assuming that each integer and floating
point number takes 4 bytes.
If you want to store millions of records, how would you improve your data structure?
Solution:
typedef struct {
int day, month, year;
} DateT;
typedef struct {
int hour, minute;
} TimeT;
typedef struct {
int transaction;
char weekday[4]; // 3 chars + terminating '\0'
DateT date;
TimeT time;
char mode; // 'B', 'F' or 'T'
char from[32], to[32];
int journey;
char faretext[12];
float fare, discount, amount;
} JourneyT;
Memory requirement for one element of type JourneyT: 4 + 4 + 12 + 8 + 1 (+ 3 padding) + 2·32 + 4 + 12 +
3·4 = 124 bytes.
The data structure can be improved in various ways: encode both origin and destination (from and to)
using Sydney Transport's unique stop IDs along with a lookup table that links e.g. 203311 to "Anzac Pde
Stand D at UNSW"; use a single integer to encode the possible "Fare Applied" entries; avoid storing
redundant information like the weekday, which can be derived from the date itself.
Problem 6. The Fibonacci numbers are defined as follows:
Fib(1) = 1
Fib(2) = 1
Fib(n) = Fib(n-1)+Fib(n-2) for n≥3
Write a C program fibonacci.c that applies the process described in Q4 to the first 10 Fibonacci numbers.
The output of the program should begin with
Fib[1] = 1
1
Fib[2] = 1
1
Fib[3] = 2
2
1
Fib[4] = 3
3
10
5
16
8
4
2
1
Solution:
#include
#define MAX 10
void collatz(int n) { // named after the German mathematician who invented this problem
printf(“%d\n”, n);
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = 3*n + 1;
}
printf(“%d\n”, n);
}
}
int main(void) {
int fib[MAX] = { 1, 1 }; // initialise the first two numbers
int i;
for (i = 2; i < MAX; i++) { // compute the first 10 Fibonacci numbers
fib[i] = fib[i-1] + fib[i-2];
}
for (i = 0; i < MAX; i++) { // apply Collatz's process to each number
printf("Fib[%d] = %d\n", i+1, fib[i]);
collatz(fib[i]);
}
return 0;
}
Problem 7. Write a C function that takes 3 integers as arguments and returns the largest of them. Your C
function cannot use any control construct.
Solution:
int max(int a, int b, int c) {
int d = a * (a >= b) + b * (a < b); // d is max of a and b
return c * (c >= d) + d * (c < d); // return max of c and d
}
Problem 8. Write a C program that takes a sequence of integers from the keyboard, sorts them, and
displays the sorted sequence on the screen, one integer per line. A non-integer indicates the end of
sequence.
Solution:
#include
#define SIZE 250
void insertionSort(int array[], int n) {
int i;
for (i = 1; i < n; i++) {
int element = array[i]; // for this element ...
int j = i-1;
while (j >= 0 && array[j] > element) { // … work down the ordered list
array[j+1] = array[j]; // … moving elements up
j–;
}
array[j+1] = element; // and insert in correct position
}
}
int main(void) {
int numbers[SIZE];
int i, n=0;
int done=1,rev;
while (done) // Initialize the array numbers[] by receiving integers from keyboard
{
if (n==SIZE-1)
break;
printf(“Type in a number \n”);
rev=scanf(“%d”, &numbers[n]);
printf(“numbers[%d]=%d\n”, n, numbers[n]);
if (rev<=0) // not an integer
done=0;
else n++;
}
insertionSort(numbers, n);
for (i = 0; i