Laboratorium 2: Wprowadzenie do programowania w C

Planowanie obliczeń jako wprowadzenie do konstrukcji algorytmów

Rozważmy problem konstrukcji liczby przez ciąg dodawań (ang. addition chain) zaczynający się od liczby 1. Np. liczbę 6 możemy uzyskać wykonując:

1 + 1 -> 2
2 + 1 -> 3
3 + 1 -> 4
4 + 1 -> 5
5 + 1 -> 6

Powyższy zapis jest projektem. Do jego realizacji użyjemy pomocniczego programu plus.c:

#include <stdio.h>
 
int main(void) {
    int x, y;
 
    scanf("%d", &x);
    scanf("%d", &y);
    printf("%d\n", x + y);
    return 0;
}

Po jego kompilacji poleceniem gcc plus.c -o plus możemy zrealizować nasz projekt ciągiem poleceń:

echo 1 > jeden
cat jeden jeden  | ./plus > dwa
cat dwa jeden    | ./plus > trzy
cat trzy jeden   | ./plus > cztery
cat cztery jeden | ./plus > piec
cat piec jeden   | ./plus > szesc

Spróbujmy teraz znaleźć najkrótszy ciąg dodawań, w wyniku którego otrzymamy 6.

Oto przykładowe rozwiązanie:

cat jeden jeden | ./plus > dwa
cat dwa jeden   | ./plus > trzy
cat trzy trzy   | ./plus > szesc

Zadanie: Najkrótszy ciąg dodawań (ang. shortest addition chain)

Znajdź najkrótszy ciąg dodawań, który da w wyniku liczbę 15.

Wprowadzenie do programowania w C

Prosimy o wpisanie poniższego programu:

#include <stdio.h>
 
int main(void) {
    int jeden, dwa, trzy, szesc;
 
    jeden = 1;
    dwa = jeden + jeden;
    trzy = dwa + jeden;
    szesc = trzy + trzy;
    printf("%d\n", szesc);
    return 0;
}

i zapamiętanie go w pliku o nazwie dodawania.c.

Ten program jest zapisem rozwiązania problemu ciągu dodawań dającego wynik 6. W stosunku do poprzednich programów, nową konstrukcją jest tu przypisanie =.

W programie:

#include <stdio.h>
 
int main(void) {
    double a, b, c, x;
 
    scanf("%lf%lf%lf%lf", &a, &b, &c, &x);
    printf("%f\n", a * x * x + b * x + c);
    return 0;
}

nowymi konstrukcjami są:

typ double,
użycie funkcji scanf do wczytania wielu wartości.

Prosimy o przetestowanie programu, w tym na danych, które nie są całkowite (uwaga: przed częścią ułamkową umieszczamy kropkę, a nie przecinek).

Zmieniamy wywołanie printf na:

    printf("%15.10f\n", a * x * x + b * x + c);

i prosimy o przetestowanie.

Zapis 15.10 wskazuje, że funkcja printf ma wypisać wartość wyrażenia w 15 znakach, 10 z nich przeznaczając na część ułamkową.

W programie:

#include <stdio.h>
 
int main(void) {
    int x, y;
 
    scanf("%d", &x);
    scanf("%d", &y);
    if (x > y) {
        printf("%d\n", x);
    } else {
        printf("%d\n", y);
    }
    return 0;
}

nowym elementem jest instrukcja warunkowa if (...) ... else ....

W programie:

#include <stdio.h>
 
int main(void) {
    int x, ile;
 
    ile = 0;
    while (scanf("%d", &x) > 0 && x != 0) {
        ++ile;
    }
    printf("Było %d\n", ile);
    return 0;
}

nowym elementem jest pętla while (...) ..., sprawdzenie wyniku funkcji scanf i koniunkcja &&.

Zwracamy uwagę na konieczność inicjalizacji zmiennej ile. Bez tego miałaby wartość nieokreśloną.

Informatyka MIMUW