C programming, Exercise solutions

Beginning exercises - Solutions

Naming

3. 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
#include
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:

double pi;
pi = 3.14;

• 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:

const float pi = 3.14;
#define pi 3.14

• Yes, for example :

int a = 67;
double b;
b = a;

• Yes, but a cast is necessary and the double is truncated:

double a=89;
int b;
b = (int) a;

Referencing

• pi2 = pi;
• The reverse, pi = pi2; is a valid C statement if pi is not a constant and pi2 is 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.

String manipulation

One possible solution could be:

#include
#include

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

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

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

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
// 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

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 // for the square root function sqrt()
#include

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

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%20||x%30)
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;
}

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
#include
#include

//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 ( , )
  */

/* 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 (2n+0) or 10 ( 2n+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
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
  #include

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+ielem_sz, a+jelem_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
#include
#include
#include
#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;
}

Where this page came from

This page was imported from Wikibooks. From “C programming” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.