forked from freudenreichan/info2Praktikum-DobleSpiel
98 lines
2.9 KiB
C
98 lines
2.9 KiB
C
#include <stdlib.h>
|
||
#include <stdio.h>
|
||
#include <time.h>
|
||
#include <string.h>
|
||
#include <stdbool.h>
|
||
#include "numbers.h"
|
||
|
||
//TODO: getDuplicate und createNumbers implementieren
|
||
/* * * Erzeugen eines Arrays mit der vom Nutzer eingegebenen Anzahl an Zufallszahlen.
|
||
* Sicherstellen, dass beim Befüllen keine Duplikate entstehen.
|
||
* Duplizieren eines zufälligen Eintrags im Array.
|
||
* in `getDuplicate()`: Sortieren des Arrays und Erkennen der doppelten Zahl durch Vergleich benachbarter Elemente. */
|
||
|
||
// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.
|
||
// Returns NULL on errors. Use your implementation of the binary search tree to check for possible duplicates while
|
||
// creating random numbers.
|
||
unsigned int *createNumbers(unsigned int len)
|
||
{
|
||
if (len < 2) {
|
||
// Mindestens zwei Elemente nötig, damit ein Duplikat existiert
|
||
return NULL;
|
||
}
|
||
|
||
unsigned int *numbers = malloc(len * sizeof(unsigned int));
|
||
if (!numbers) return NULL;
|
||
|
||
bool *used = calloc(2 * len + 1, sizeof(bool));
|
||
if (!used) {
|
||
free(numbers);
|
||
return NULL;
|
||
}
|
||
|
||
static int initialized = 0;
|
||
if (!initialized) {
|
||
srand((unsigned int)time(NULL));
|
||
initialized = 1;
|
||
}
|
||
|
||
// Einzigartige Zufallszahlen generieren
|
||
for (unsigned int i = 0; i < len - 1; ) {
|
||
unsigned int num = (rand() % (2 * len)) + 1;
|
||
if (!used[num]) {
|
||
used[num] = true;
|
||
numbers[i++] = num;
|
||
}
|
||
}
|
||
|
||
// Eine der Zahlen duplizieren
|
||
unsigned int duplicateIndex = rand() % (len - 1);
|
||
numbers[len - 1] = numbers[duplicateIndex];
|
||
|
||
// Fisher–Yates shuffle
|
||
for (unsigned int i = len - 1; i > 0; i--) {
|
||
unsigned int j = rand() % (i + 1);
|
||
unsigned int tmp = numbers[i];
|
||
numbers[i] = numbers[j];
|
||
numbers[j] = tmp;
|
||
}
|
||
|
||
free(used);
|
||
return numbers;
|
||
}
|
||
|
||
// Returns only the only number in numbers which is present twice. Returns zero on errors.
|
||
unsigned int getDuplicate(const unsigned int numbers[], unsigned int len)
|
||
{
|
||
if (numbers == NULL || len < 2) {
|
||
return 0;
|
||
}
|
||
|
||
unsigned int *sortedNumbers = malloc(len * sizeof(unsigned int));
|
||
if (sortedNumbers == NULL) {
|
||
return 0;
|
||
}
|
||
memcpy(sortedNumbers, numbers, len * sizeof(unsigned int));
|
||
|
||
// Einfacher bubble sort
|
||
for (unsigned int i = 0; i < len - 1; i++) {
|
||
for (unsigned int j = 0; j < len - i - 1; j++) {
|
||
if (sortedNumbers[j] > sortedNumbers[j + 1]) {
|
||
unsigned int temp = sortedNumbers[j];
|
||
sortedNumbers[j] = sortedNumbers[j + 1];
|
||
sortedNumbers[j + 1] = temp;
|
||
}
|
||
}
|
||
}
|
||
|
||
unsigned int duplicate = 0;
|
||
for (unsigned int i = 0; i < len - 1; i++) {
|
||
if (sortedNumbers[i] == sortedNumbers[i + 1]) {
|
||
duplicate = sortedNumbers[i];
|
||
break;
|
||
}
|
||
}
|
||
|
||
free(sortedNumbers);
|
||
return duplicate;
|
||
} |