Exercise solutions
Beginning exercises - Solutions
Variables
Naming
-
Give an example of a C variable name that would not work. Why doesn't it work?
-
No, the name of a variable must begin with a letter (lowercase or uppercase), or an underscore.
- Only the underscore can be used.
- for example, #nm*rt is not allowed because # and * are not the valid characters for the name of a variable.
#include <stdio.h>
#include <stdlib.h>
main()
{
int a, b, c, max;
#ifdef __WIN32
system("cls"); // for Windows
#else
system("clear"); // for Unix and Linux
#endif
printf("\n enter three numbers ");
scanf(" %d %d %d ",&a,&b,&c);
max = a;
if(max < b)
max = b;
if(max < c)
max = c;
printf("\n largest=%d \n",max);
getchar();
}
Data types
1.1. On your computer, how much memory does each require?
- 3 data types : long int, short int,float.
- On my computer :
- long int : 4 bytes
- short int : 2 bytes
- float : 4 bytes
- we can not use 'int' or 'float' as a variable's name.
Assignment
- The standard way of assigning 3.14 to pi is:
-
- Since pi is a constant, good programming convention dictates to make it unchangeable during runtime. Extra credit if you use one of the following two lines:
- Yes, for example :
- Yes, but a cast is necessary and the double is truncated:
Referencing
pi2 = pi;- The reverse,
pi = pi2;is a valid C statement ifpiis not a constant andpi2is initialized. - a.
pi2 = 3.1415;
b. The reverse:3.1415 = pi2;is not valid since it is impossible to assign a value to a literal.
Simple I/O
String manipulation
One possible solution could be:
#include <stdio.h>
#include <string.h>
int main(void)
{
char s[81]; // A string of upto 80 chars + '\0'
int i;
puts("Please write a string: ");
fgets(s, 81, stdin);
puts("Your sentence in reverse: ");
for (i= strlen(s)-1; i >= 0; i--)
{
if (s[i] == '\n')
continue; // don't write newline
else
putchar(s[i]);
}
putchar('\n');
return 0;
}
#define __STDC_WANT_LIB_EXT1__ 1 // Active C11 extended functions (this case is gets_s)
#include<stdio.h>
int slen(const char *); // I don't want to include whole string lib just for get size
int main(void) {
char s[500];
printf("%s","Enter a sentence: ");
if(!gets_s(s,500)) {
puts("Error!");
getchar();
return 0;
}
for(int i=0;i<slen(s);i++)
if(s[i]!=32)
putchar(s[i]);
else
putchar(10);
putchar(10);
getchar();
return 0;
}
int slen(const char *s) {
int i;
for(i=0;s[i]!=0;i++);
return i;
}
Loops
One possible solution:
#include<stdio.h>
int main(void) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return 0;
}
One possible solution:
#include<stdio.h>
int main(void) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return 0;
}
One possible solution:
#include<stdio.h>
// This is the fastest way
int main(void) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++)
putchar(42);
putchar(10);
}
for(int i=n-1;i>0;i--) {
for(int j=0;j<i;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return 0;
}
or like this (all math)
void sideways(int n)
{
int i=0,j=0;
for(i=1;i<2*n;i++){
for(j=1;j<=(n-(abs(n-i)));j++){
printf("*");
}
printf("\n");
}
}
One possible solution:
void right_side_up(int n)
{
int x,y;
for (y= 1; y <= n; y++)
{
for (x= 0; x < n-y; x++)
putchar(' ');
for (x= (n-y); x < (n-y)+(2*y-1); x++)
putchar('*');
putchar('\n');
}
}
Another solution:
#include<stdio.h>
int main(void) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
for(int j=0;j<n-i-1;j++)
putchar(32);
for(int j=0;j<i*2+1;j++)
putchar(42);
putchar(10);
}
while((n=getchar())!=10);
getchar();
return 0;
}
Math
// to compile: gcc -Wall prime.c -lm -o prime
#include <math.h> // for the square root function sqrt()
#include <stdio.h>
int is_prime(int n);
int main()
{
printf("Write an integer: ");
int var;
scanf("%d", &var);
if (is_prime(var)==1) {
printf("A prime\n");
} else {
printf("Not a prime\n");
}
return 1;
}
int is_prime(int n)
{
int x;
int sq= sqrt(n)+1;
// Checking the trivial cases first
if ( n < 2 )
return 0;
if ( n == 2 || n == 3 )
return 1;
// Checking if n is divisible by 2 or odd numbers between 3 and the
// square root of n.
if ( n % 2 == 0 )
return 0;
for (x= 3; x <= sq; x += 2)
{
if ( n % x == 0 )
return 0;
}
return 1;
}
Another better solution that doesn't need to include math.h and faster than the one above.
#include<stdio.h>
int isPrime(const unsigned long long int);
int main(void) {
unsigned long long n;
scanf("%llu",&n);
printf("%d\n",isPrime(n));
while((n=getchar())!=10);
getchar();
return 0;
}
int isPrime(const unsigned long long int x) {
if(x<4)
return x>1;
if(x%2==0||x%3==0)
return 0;
for(unsigned long int i=5;i*i<=x;i+=6)
if(x%i==0||x%(i+2)==0)
return 0;
return 1;
}
Recursion
Merge sort
One possible solution , after reading online descriptions of recursive merge sort, e.g. Dasgupta :
// to compile: gcc -Wall rmergesort.c -lm -o rmergesort
/*
============================================================================
Name : rmergesort.c
Author : Anon
Version : 0.1
Copyright : (C)2013 under CC-By-SA 3.0 License
Description : Recursive Merge Sort, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//const int MAX = 200;
const int MAX = 20000000;
int *b;
int printOff = 0;
// this debugging print out of the array helps to show
// what is going on.
void printArray(char* label, int* a, int sz) {
int h = sz/ 2;
int i;
if (printOff) return;
printf("\n%s:\n", label);
for (i = 0; i < h; ++i ) {
printf("%d%c", a[i],
// add in a newline every 20 numbers
( ( i != 0 && i % 20 == 0 )? '\n': ' ' ) );
}
printf(" | ");
for (;i < sz; ++i) {
printf("%d%c", a[i],
( ( i != 0 && i % 20 == 0 )? '\n': ' ' ) );
}
putchar('\n');
}
void mergesort(int* a, int m ) {
printArray("BEFORE", a, m);
if (m > 2) {
// if greater than 2 elements, then recursive
mergesort(a, m / 2);
mergesort(a + m / 2, m - m / 2);
} else if (m == 2 && a[0] > a[1]) {
// if exactly 2 elements and need swapping, swap
int t = a[1];
a[1] = a[0];
a[0] = t;
goto end;
}
// 1 or greater than 2 elements which have been recursively sorted
// divide the array into a left and right array
// merge into the array b with index l.
int n = m/2;
int o = m - n;
int i = 0, j = n;
int l = 0;
// i is left, j is right ;
// l should equal m the size of the array
while (i < n) {
if ( j >= m) {
// the right array has finished, so copy the remaining left array
for(; i < n; ++i) {
b[l++] = a[i];
}
// the merge operation is to copy the smaller current element and
// increment the index of the parent sub-array.
} else if( a[i] < a[j] ) {
b[l++] = a[i++];
} else {
b[l++] = a[j++];
}
}
while ( j < m) {
// copy the remaining right array , if any
b[l++] = a[j++];
}
memcpy(a, b, sizeof(int) * l );
end:
printArray("AFTER", a, m);
return;
}
void rand_init(int* a, int n) {
int i;
for (i = 0; i < n; ++i ) {
a[i] = rand() % MAX;
}
}
int main(void) {
puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */
// int N = 20;
// int N = 1000;
// int N = 1000000;
int N = 100000000; // still can't make a stack overflow on ubuntu,4GB, phenom
printOff = 1;
int *a;
b = calloc( N, sizeof(int));
a = calloc( N, sizeof(int));
rand_init(a, N);
mergesort(a, N);
printOff = 0;
printArray("LAST", a, N);
free(a);
free(b);
return EXIT_SUCCESS;
}
/* Having failed to translate my concept of non-recursive merge sort,
* I tackled the easier case of recursive merge sort.
* The next task is to translate the recursive version to a non-recursive
* version. This could be done by replacing calls to mergesort, with
* pushes onto a stack of
* tuples of ( <array start address>, <number of elements to process> )
*/
/* The central idea of merging, is that two sorted lists can be
* merged into one sorted list, by comparing the top of each list and
* moving the lowest valued element onto the end of the new list.
* The other list which has the higher valued element keeps its top
* element unchanged. When a list is exhausted, copy the remaining other list
* onto the end of the new list.
*/
/* The recursive part, is to defer any work in sorting an unsorted list,
* by dividing it into two lists until there is only 1 or two elements,
* and if there are two elements, sort them directly by swapping if
* the first element is larger than the second element.
*
* After returning from a recursive call, merge the lists, which will
* begin with one or two element sorted lists. The result is a sorted list
* which will be returned to the parent of the recursive call, and can
* be used for merging.
*/
/* The following is an imaginary discussion about what a programmer
* might be thinking about when programming:
*
* Visualising recursion in terms of a Z80 assembly language, which
* is similar to most assembly languages, there is a data stack (DS) and
* a call stack (CS) pointer, and each recursive call to mergesort
* pushes the return address , which is the program address of the instruction
* after the call , onto the stack pointed to by CS and CS is incremented,
* and the address of the array start and integer which is the subarray length
* onto the data stack pointed to by DS, which will be incremented twice.
*
* If the number of recursive , active calls exceed the allowable space for either the call stack
* or the data stack, then the program will crash , or a process space protection
* violation interrupt signal will be sent by the CPU, and the interrupt vector
* for that signal will jump the processor's current instruction pointer to the
* interrupt handling routine.
*/
Binary heaps
- 10, 4, 6, 3, 5, 11 -> 10
- 4, 6,3, 5, 11 -> 10, 4 : 4 is end-added, no swap-parent because 4 \< 10.
- 6, 3, 5, 11 -> 10, 4, 6 : 6 is end-added, no swap-parent because 6 \< 10.
- 3, 5, 11 -> 10, 4, 6, 3 : 3 is end-added, 3 is position 4 , divide by 2 = 2, 4 at position 2, no swap-parent because 4 > 3.
-
5 , 11 -> 10, 4, 6, 3 , 5 : 5 is end-added , 5 is position 5, divided by 2 = 2, 4 at position 2, swap-parent as 4 \< 5; 5 at position 2, no swap-parent because 5 \< 10 at position 1.
-
10 , 5, 6, 3, 4
-
11 -> 10, 5, 6, 3, 4, 11 : 11 is end-added, 11 is position 6, divide by 2 = 3, swap 6 with 11, 11 is position 3, swap 11 with 10, stop as no parent.
-
11, 5, 10, 3, 4, 6
-
11 has children 5, 10 ; 5 has children 3 and 4 ; 10 has child 6. Parent always > child.
-
11 leaves * , 5, 10, 3, 4, 6 -> 6 , 5, 10, 3, 4 -> sift-down -> choose greater child 5 (2*n+0) or 10 ( 2*n+1) -> is 6 > 10 ? no -> swap 10 and 6 ->
-
10, 5, *6, 3, 4 -> 4 is greatest child as no +1 child. is 6 > 4 ? yes, stop.
-
10 leaves * , 5 , 6 , 3, 4 -> *4, 5, 6, 3 -> is left(0) or right(+1) child greater -> +1 is greater; is 4 > +1 child ? no , swap
-
6,5, *4, 3 -> *4 has no children so stop.
-
6 leaves *, 5, 4, 3 -> *3, 5, 4 -> +0 child is greater -> is 3 > 5 ? no , so swap -> 5, *3, 4 , *3 has no child so stop.
is
-
5 leaves so 3, 4 -> *4, 3 -> +0 child greatest as no right child -> is 4 > 3 ? no , so exit
-
4 leaves 3 .
-
3 leaves *.
-
numbers extracted in descending order 11, 10, 6, 5, 4, 3.
Quick sort
One possible solution , can be to adapt this word sorting use of quicksort to sort integers. Otherwise , an exercise would be to re-write non-generic qsort functions of qsortsimp, partition, and swap for integers.
/*
* qsortsimp.h
*
* Created on: 17/03/2013
* Author: anonymous
*/
#ifndef QSORTSIMP_H_
#define QSORTSIMP_H_
#include <stdlib.h>
void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) );
void shutdown_qsortsimp();
#endif /* QSORTSIMP_H_ */
//----------------------------------------------------------------------------
/* qsortsimp.c
* author : anonymous
*/
#include "qsortsimp.h"
#include<stdlib.h>
#include<string.h>
static void * swap_buf =0;
static int bufsz = 0;
void swap( void* a, int i, int j, size_t elem_sz) {
if (i==j)return;
if (bufsz == 0 || bufsz < elem_sz) {
swap_buf = realloc(swap_buf, elem_sz);
bufsz=elem_sz;
}
memcpy( swap_buf, a+i*elem_sz, elem_sz);
memcpy( a+i*elem_sz, a+j*elem_sz, elem_sz);
memcpy( a+j*elem_sz, swap_buf, elem_sz);
}
void shutdown_qsortsimp() {
if (swap_buf) {
free(swap_buf);
}
}
int partition( void* a, size_t elem_sz, int len, int (*cmp)(void*,void*) ) {
int i = -1;
int j = len-1;
void* v = a + j * elem_sz;
for(;;) {
while( (*cmp)(a + ++i * elem_sz , v ) < 0);
while ( (*cmp)(v, a + --j * elem_sz) < 0 ) if (j==0) break ;
if( i>=j)break;
swap(a, i, j, elem_sz);
}
swap( a, i, len-1, elem_sz);
return i;
}
void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) ) {
if ( len > 2) {
int p = partition(a, elem_sz, len, cmp);
qsortsimp( a, elem_sz, p, cmp);
qsortsimp( a+(p+1)*elem_sz, elem_sz, len - p -1, cmp );
}
}
//------------------------------------------------------------------------------
/*
Name : words_quicksort.c
Author : anonymous
Version :
Copyright :
Description : quick sort the words in moby dick in C, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "qsortsimp.h"
void printArray(const char* a[], int n) {
int i;
for(i=0; i < n; ++i) {
if(i!=0 && i% 5 == 0) {
printf("\n");
}
if (i%1000000 ==0) {
fprintf(stderr,"printed %d words\n", i);
}
printf("%s ", a[i]);
}
printf("\n");
}
const int MAXCHARS=250;
char ** wordlist=0;
int nwords=0;
int remaining_block;
const size_t NWORDS_PER_BLOCK = 1000;
//const char* spaces=" \t\n\r";
//inline isspace(const char ch) {
// int i=0;
// while(spaces[i]!='\0') {
// if(spaces[i++] == ch)
// return 1;
// }
// return 0;
//}
void freeMem() {
int i = nwords;
while(i > 0 ) {
free(wordlist[--i]);
}
free(wordlist);
}
static char * fname="~/Downloads/books/pg2701-moby-dick.txt";
void getWords() {
char buffer[MAXCHARS];
FILE* f = fopen(fname,"r");
int state=0;
int ch;
int i;
while ((ch=fgetc(f))!=EOF) {
if (isalnum(ch) && state==0) {
state=1;
i=0;
buffer[i++]=ch;
} else if (isalnum(ch) && i < MAXCHARS-1) {
buffer[i++]=ch;
} else if (state == 1) {
state =0;
buffer[i++]= '\0';
char* dynbuf = malloc(i);
int j;
for(j=0; j < i; ++j) {
dynbuf[j] = buffer[j];
}
i=0;
if (wordlist == 0 ) {
wordlist = calloc(NWORDS_PER_BLOCK, sizeof(char*));
remaining_block = NWORDS_PER_BLOCK;
} else if ( remaining_block == 0) {
wordlist = realloc(wordlist, (NWORDS_PER_BLOCK + nwords)* sizeof(char*));
remaining_block = NWORDS_PER_BLOCK;
fprintf(stderr,"allocated block %d , nwords = %d\n", remaining_block, nwords);
}
wordlist[nwords++]= dynbuf;
--remaining_block;
}
}
fclose(f);
}
void testPrintArray() {
int i;
for(i=0; i < nwords;++i) {
printf("%s | ", wordlist[i]);
}
putchar('\n');
printf("stored %d words. \n",nwords);
}
int cmp_str_1( void* a, void *b) {
int r = strcasecmp( *((char**)a),*((char**)b));
return r;
}
int main(int argc, char* argv[]) {
if (argc > 1) {
fname = argv[1];
}
getWords();
testPrintArray();
qsortsimp(wordlist, sizeof(char*), nwords, &cmp_str_1);
testPrintArray();
shutdown_qsortsimp();
freeMem();
puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */
return EXIT_SUCCESS;
}
Source: Wikibooks – Exercise solutions. Licensed under CC BY-SA 3.0.