Design and Analysis of Algorithms Week 3: Assignment - Unicheck Review
kinjalr10
Lesson3a.docxIT 206: Design and Analysis of Algorithms
Lesson 3
Example: Maximum value
#include <stdio.h>
int main()
{
int n = 5;
int numbers[n], i, maxval;
printf("Enter five integers: ");
for (int i = 0; i<n; i++)
{scanf("%d", &numbers[i]);
// print the numbers inputted
printf("\nThe numbers are %d", numbers[i]);
}
maxval = numbers[0];
for (i=1; i<n; i++)
{
if (numbers[i] > maxval)
maxval = numbers[i];
}
printf("\nThe maximum value is: %d", maxval);
return 0;
}
Write an algorithm for the situation below for 1 soldier. Then rewrite it for 2 soldiers.
Ferrying soldiers
A detachment of n soldiers must cross a wide and deep river with no bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one soldier. How can the soldiers get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?
Bubble Sort
#include <stdio.h>
int main()
{
void BubbleSort(int A[], int n){
for (int pass = n-1; pass>=0; pass--){
for (int i = 0; i<= pass-1; i++){
if (A[i]>A[i+1]){
//swap elements
int temp = A[i];
A[i] = A[i+1];
A[i+1] = temp;
}
}
}
}
int A[] = {89, 45, 68, 90, 29, 34, 17};
int n = 7;
BubbleSort(A, n);
for (int i=0; i<=n; i++)
printf("\n %d",A[i]);
}
Second version
#include <stdio.h>
void bubble_sort(long [], long);
int main()
{
long array[100], n, c, d, swap;
printf("Enter number of elements\n");
scanf("%ld", &n);
printf("Enter %ld integers\n", n);
for (c = 0; c < n; c++)
scanf("%ld", &array[c]);
bubble_sort(array, n);
printf("Sorted list in ascending order:\n");
for ( c = 0 ; c < n ; c++ )
printf("%ld\n", array[c]);
return 0;
}
void bubble_sort(long list[], long n)
{
long c, d, t;
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (list[d] > list[d+1])
{
/* Swapping */
t = list[d];
list[d] = list[d+1];
list[d+1] = t;
}
}
}
}
