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ę

/* Przykad 2a ver.1 */

#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 );

}

/* Przykad 2a ver. 3 */

#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 );

}

/* Przykad 2a ver. 4 */

#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

/* Przykad 2b ver.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

ZADANIE 3 (domowe):

znajdź największy wspólny podzielnik

dwóch liczb naturalnych