Zettel 06

Aufgabe 1

circular_buffer.cc (auch im Zip enthalten)

Um die Lesbarkeit der Ausgabe zu vereinfachen interpretieren wir 0 als leeres Slot. Somit wenn ein slot gelesen wird, wird sein Wert durch 0 ersetzt, d.h. ‘geloescht’.

#include <stdio.h>
#define N 10

int buffer [N];

int w = 0; //write index
int r = 0; //read index 

int use_size = 0; //count of the elements in buffer

int read()
{
    if (use_size == 0) //buffer empty, return error code -1
        return -1;
    int i = r; //i holds current read index 
    r = (r + 1) % N; //increment read index modulo N
    use_size--; //one less element in the buffer, decrement size
    int output = buffer[i];
    buffer[i] = 0; //0 value corresponds to an empty slots, i.e. deletion of an element
    return output;
}

void write (int item)
{
    if (use_size == N){ //buffer full, overwrite with warning. 
        printf("Warning: buffer full, overwriting oldest element!\n");
        buffer[w] = item;
        w = (w + 1) % N; //increment write index modulo N
        r = w; //when buffer full w == r is true
    } 
    else {
        buffer[w] = item;
        w = (w + 1) % N;
        use_size++;
    } 
}

void print_buffer()
{
    printf("buffer = [\n");
    for (int i = 0; i < N; i++){
        if (w != i && r != i) printf("  %d\n", buffer[i]);
        if (w != i && r == i) printf("< %d\n", buffer[i]);
        if (w == i && r != i) printf("> %d\n", buffer[i]);
        if (w == i && r == i) printf("><%d\n", buffer[i]);
    }
    printf("]\n\n");
};

int main()
{
    //initialize buffer
    for (int i = 0; i < N; i++) buffer[i] = 0; //since buffer contains only positive
                                               // set everything initially to 0 representing empty slots
    int i = 13497 % N; //or any other initial random index
    buffer[i] = 1; //set the slot in this index to 1, everything else is 0
    r = i; //initial read index 
    w = (i + 1) % N; //initial write index 
    use_size = 1; //initially one element in buffer

    int input; //menu option
    do {
        printf("input: ");
        scanf("%d", &input);
        if (input == -1) break;
        else if (input == 0){
            int item = read();
            if (item == -1) printf("buffer is empty\n");
            else {
                printf("\nout: %d\n", item);
                print_buffer();
            }
        } else if (input > 0){
                write(input);
                print_buffer();
        } else printf("invalid option!\n");
 
    } while (input != -1);
    return 0;
}

Aufgabe 2

• 8 mal fuer out-shuffle
• 52 mal fuer in-shuffle

shuffle.cc (siehe zip).

#include <stdio.h>
#include <iostream>
#define N 52

int deck[N];

//we need this division operation to cover cases when n is odd
//because for odd n we want to get ceiling(n/2) and use it when copying arrays in the shuffle functions
//otherwise the indices don't quite work for odd cases the way we implement shuffle functions
int div2(int n)
{
    if (n & 1) return n/2 + 1;
    return n/2;
}

bool deck_check(int deck[], int n)
{
    for (int i = 0; i < n; i++){
        if(i != deck[i]) return false;
    }
    return true;
}

void out_shuffle(int deck[], int n)
{
    int temp[n];
    //write shuffled values to temp
    for (int i = 0; i < div2(n); i++) temp[2*i] = deck[i]; //even indices get upper half of deck
    for (int i = 0; i < div2(n); i++) temp[2*i + 1] = deck[div2(n) + i]; //odd indices get lower half of deck
    //write temp to deck
    for (int i = 0; i < n; i++) deck[i] = temp[i];
}

void in_shuffle(int deck[], int n)
{
    int temp[n];
    for (int i = 0; i < n/2; i++) temp[2*i + 1] = deck[i]; //odd indices get upper half of the deck
    for (int i = 0; i < div2(n); i++) temp[2*i] = deck[n/2 + i]; //odd indices get upper half of the deck
    for (int i = 0; i < n; i++) deck[i] = temp[i];
}

int main()
{
    //initialize deck for out-shuffling
    for (int i = 0; i < N; i++) deck[i] = i;

    out_shuffle(deck, N); //deck out-shuffled once
    int count = 1; //how many times have the deck been shuffled? 
    while (!deck_check(deck, N)){
        out_shuffle(deck, N);
        count++;
    }
    printf("how many times to repeat out-shuffle to get initial configuration? %d\n", count);


    //initialize deck for in-shuffling
    for (int i = 0; i < N; i++) deck[i] = i;

    in_shuffle(deck, N); //deck in-shuffled once
    count = 1; //how many times have the deck been shuffled? 
    while (!deck_check(deck, N)){
        in_shuffle(deck, N);
        count++;
    }
    printf("how many times to repeat in-shuffle to get initial configuration? %d\n", count);

    // some simple tests below, not relevant to the problem
    // for (int i = 0; i < N; i++) deck[i] = i;
    // for (int i = 0; i < N; i++) printf("%d %d\n", i, deck[i]);
    // printf("\n\n");
    // in_shuffle(deck, N);
    // for (int i = 0; i < N; i++) printf("%d %d\n", i, deck[i]);
    // printf("\n\n");

    return 0;
}

Aufgabe 3