LECTURE 7
Problem → Algorithm (block diagram) → Program →
→ Program debugging (error removal)
Simple mathematical exercises
Programs: e2_1.c ......, e2_6.c
Tomasz Zieliński
EXERCISE 1 (programs: e2_1, e2_2, e2_3, e2_4) : express any natural number as a multiplication of prime numbers e.g. 8 = 2*2*2, 15 = 3*5, 24 = 2*2*2*3
=====================================================
NEW:
REPEAT:
Is the reminder
Choose a
Increase
of division
Is x greater
number x
Initialize
divisor
equal 0?
than 1?
NO
NO
START
x = ?
d =1
d=d+1
x%d==0
x > 1
STOP
ix = 0
table
px[ix]=d
YES
YES
px[ ]
ix = ix+1
d
– number tested as a divisor
px[ix]=d
finally, next divisor value
x=x/d
ix
– divisor index
px[.] – table of divisors
Increase index ix by 1
Store divisor d into the table
Divide the number x
#include <stdio.h>
#define MAXSIZE 100
main()
{
unsigned int x, d, px[ MAXSIZE ], ix, i; printf(" \n Please, choose a natural number to be decomposed ? " ); scanf("%d", &x);
d = 1; ix = 0; px[ ix ] = d;
NEW:
d = d + 1;
/* or d += 1, d++ */
REPEAT:
if ( x % d == 0 )
/* reminder from division of number x by d */
{
ix = ix + 1;
px[ ix ] = d;
x = x / d;
/* lub x /= d */
goto REPEAT;
}
else
{ if ( x > 1 ) goto NEW; }
for( i = 0; i <= ix; i++ ) { printf( " %5d", px[ i ] ); }
return( 0 );
}
#include <stdio.h>
#define MAXSIZE 100
main()
{
unsigned int x, d, px[ MAXSIZE ], ix, i; printf(" \n Please, choose a natural number to be decomposed? " ); scanf("%d", &x); d = 1; ix = 0; px[ ix ] = d;
do
{
d = d + 1;
/* lub d += 1, d++ */
while ( x % d == 0 )
{
ix = ix + 1;
px[ ix ] = d;
x = x / d;
/* x /= d */
}
}
while ( x != 1 );
for( i = 0; i <= ix; i++ ) { printf( " %5d", px[ i ] ); }
return( 0 );
}
#include <stdio.h> /* functions: printf i scanf */
#include <stdlib.h> /* functions: malloc i free */
#define MAXSIZE 100
main()
{
unsigned int x, *px, *wpx1, *wpx2;
// declarations of pointers to memory (to unsigned int) unsigned int d;
// memory allocation for pointers is done below px = (unsigned int *) malloc( MAXSIZE * sizeof( int ) ); wpx1 = px; wpx2 = px; printf(" \n Please, choose a natural number to be decomposed? "); scanf("%d", &x); d = 1; *px = d;
// write value d into memory under the address do {
// specified by pointer px
d++;
while ( x % d == 0 )
{
*(++px) = d;
// first increase the pointer value, then store the value of d x = x / d;
// since px is a pointer to unsigned int, 16 bits are skipped
}
} while ( x != 1 );
while ( wpx1 <= px ) { printf( " %5d", *wpx1++ ); } // first print divisor value, then increase wpx1
free(
wpx2
);
// free memory associated with wpx2, return( 0 );
// allocated by malloc function
}
EXERCISE 2 - algorithm 1 (pogram c2_5) : find the smallest common multiple for two natural numbers „x” i „y”
e.g. 4 and 5 ⇒ 20, 2 and 6 ⇒ 6 not 12, 6 and 8 ⇒ 24 not 48
x
x
x
y
y
y
y
y
YES
x = ?
ix = 1
mx = ix*x
START
mx == my
Print mx
STOP
y = ?
iy = 1
my = iy*y
NO
x, y
– given numbers
YES
ix, iy
– how many times of x and y
ix = ix+1
mx < my
mx, my – multiples of x and y
NO
iy = iy+1
#include <stdio.h>
void main()
{
long x, y, mx, my, ix, iy;
printf( "\n Please, give two natural numbers: " ); scanf("%ld %ld", &x, &y); printf("\n");
ix = 1; iy = 1;
mx = ix * x; my = ix * y;
/* first multiples */
while ( mx != my )
/* if not equal */
{
if ( mx > my )
/* if mx > my */
iy++;
else
ix++;
mx = ix * x;
/* next multiples */
my = iy * y;
}
printf("The smallest common multiple = %ld\n", mx);
}
EXERCISE 2 - algorithm 2 (program c2_6) : find the smallest common multiple for two natural numbers „x” i 2*2*2 * 6 = 2*3 * 8 = 24
8
6
==========================================================================================================
START
x = ?
y = ?
{ px[.], ixmax } = prime_numbers(x)
{ py[.], iymax } = prime_numbers (y) ix = 0
iy = 0
NO
YES
YES
px[ix] > py[iy]
iy = iy+1
iy > iymax
NO
NO
YES
YES
px[ix] < py[iy]
ix = ix+1
ix > imax
NO
px[ix] = 1; ix = ix +1
YES
ix > ixmax
NO
iy = iy+1
YES
iy > iymax
NO
Print: px[0] * px[1] *... *px[ixmax] * y STOP
EXERCISE 3 (homework): find the greatest common divisor
for two natural numbers “x” and “y