WYKŁAD 7
Problem → Algorytm (schemat blokowy) → Program →
→ Uruchamianie programu (usuwanie błędów) Proste zadania matematyczne
Programy: c2_1.c ......, c2_6.c
Tomasz Zieliński
ZADANIE 1 (programy c2_1, c2_2, c2_3, c2_4) : przedstaw dowolną liczbę naturalną jako iloczyn liczb pierwszych np. 8 = 2*2*2, 15 = 3*5, 24 = 2*2*2*3
=====================================================
NOWE:
POWTÓRZ:
czy reszta
czy liczba
podaj
zwiększ
z dzielenia
jest już
liczbę
inicjalizacja
liczbę
równa 0?
równa 0?
NIE
NIE
START
x = ?
d =1
d=d+1
x%d==0
x != 1
Wydruk
STOP
ix = 0
tablicy
px[ix]=d
TAK
TAK
px[ ]
ix = ix+1
d
– kolejny dzielnik
px[ix]=d
ix
– indeks dzielnika
x=x/d
px[.] – tablica dzielników
zwiększ indeks
zapisz dzielnik do tablicy
podziel liczbę
#include <stdio.h>
#define MAXSIZE 100
main()
{
unsigned int x, d, px[ MAXSIZE ], ix, i; printf(" \n Jaka liczba naturalna ? " ); scanf("%d", &x);
d = 1; ix = 0; px[ ix ] = d;
NOWE:
d = d + 1;
/* lub d += 1, d++ */
POWTORZ: if ( x % d == 0 )
/* reszta z dzielenia x przez d */
{
ix = ix + 1;
px[ ix ] = d;
x = x / d;
/* lub x /= d */
goto POWTORZ;
}
else
{ if ( x != 1 ) goto NOWE; }
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 Jaka liczba naturalna ? " ); 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> /* funkcje: printf i scanf */
#include <stdlib.h> /* funkcje: malloc i free */
#define MAXSIZE 100
main()
{
unsigned int x, *px, *wpx1, *wpx2; // deklaracja wskaźników do pamięci unsigned int d;
// poniżej przydzielenie pamięci
px = (unsigned int *) malloc( MAXSIZE * sizeof( int ) ); wpx1 = px; wpx2 = px; printf(" \n Jaka liczba naturalna ? "); scanf("%d", &x); d = 1; *px = d;
// zapisz do pamięci pod adres
do {
// pokazywany przez wskaźnik
d++;
while ( x % d == 0 )
{
*(++px)
=
d;
// najpierw zwiększ wskaźnik, potem zapisz x = x / d;
}
} while ( x != 1 )
while ( wpx1 <= px ) { printf( " %5d", *wpx1++ ); } // najpierw zapisz, potem zwiększ wpx1
free( wpx2 );
// zwolnij pamięć związaną ze wskaźnikiem, return( 0 );
// przydzieloną funkcją malloc
}
ZADANIE 2 - algorytm 1 (pogram c2_5) : znajdź najmniejszą wspólną wielokrotność dwóch liczb naturalnych „x” i „y”
np. 4 i 5 ⇒ 20, 2 i 6 ⇒ 6 a nie 12, 6 i 8 ⇒ 24 a nie 48
x
x
x
y
y
y
y
y
TAK
x = ?
ix = 1
wx = ix*x
START
wx == wy
Wydruk wx
STOP
y = ?
iy = 1
wy = iy*y
NIE
x, y
– podane liczby
TAK
ix, iy
– ile razy x oraz y
ix = ix+1
wx < wy
wx, wy – wielokrotności x oraz y
NIE
iy = iy+1
#include <stdio.h>
void main()
{
long x, y, wx, wy, ix, iy;
printf( "\n Jakie dwie liczby naturalne ? " ); scanf("%ld %ld", &x, &y); printf("\n");
ix = 1; iy = 1;
wx = ix * x; wy = ix * y;
/* pierwsze wielokrotnosci */
while ( wx != wy )
/* jesli rozne */
{
if ( wx > wy )
iy++;
else
ix++;
wx = ix * x;
/* kolejne wielokrotnosci */
wy = iy * y;
}
printf("najmniejsza wspolna wielokrotnosc = %ld\n", wx);
}
ZADANIE 2 - algorytm 2 (program c2_6) : znajdź najmniejszą wspólną wielokrotność dwóch liczb naturalnych
2*2*2 * 6 = 2*3 * 8 = 24
8
6
==========================================================================================================
START
x = ?
y = ?
{ px[.], ixmax } = iloczyn(x)
{ py[.], iymax } = iloczyn(y)
ix = 0
iy = 0
NIE
TAK
TAK
px[ix] > py[iy]
iy = iy+1
iy > iymax
NIE
NIE
TAK
TAK
px[ix] < py[iy]
ix = ix+1
ix > imax
NIE
px[ix] = 1; ix = ix +1
TAK
ix > ixmax
NIE
iy = iy+1
TAK
iy > iymax
NIE
Wydruk: px[0] * px[1] *... *px[ixmax] * y STOP
znajdź największy wspólny podzielnik
dwóch liczb naturalnych