Jump to content

C Programming/Exercise solutions

Add links
From Wikibooks, open books for an open world
  1. include<stdio.h>
  2. define a5+2

Into main() { 

       Into ans;

Ans=a*a*a; Printf("%d",c) ; Return 0; }

Beginning Exercises - Solutions

[edit | edit source]

Variables

[edit | edit source]

Naming

[edit | edit source]

3. Give an example of a C variable name that would not work. Why doesn't it work?

  1. No, the name of a variable must begin with a letter (lowercase or uppercase), or an underscore.
  2. Only the underscore can be used.
  3. 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

[edit | edit source]

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

[edit | edit source]
  • 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

[edit | edit source]
  1. pi2 = pi;
  2. The reverse, pi = pi2; is a valid C statement if pi is not a constant and pi2 is initialized.
  3. 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

[edit | edit source]

String manipulation

[edit | edit source]

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

[edit | edit source]

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

[edit | edit source]
// 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

[edit | edit source]

Merge sort

[edit | edit source]

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

[edit | edit source]
  • 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

[edit | edit source]

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;
}
Retrieved from "https://en.wikibooks.org/w/index.php?title=C_Programming/Exercise_solutions&oldid=4438652"