Juhuu, mit dem Ansatz schaffe ich es auf dem C64 in unter einer Minute für alle 10.000 Codes den Folgecode zu berechnen, zu prüfen ob jeder Code genau *einen* Vorgänger hat → alles Kreise, und die Gruppen/Kreise zu bestimmen/markieren. Ausgabe:
[codebox=text file=Unbenannt.txt]run
Folgecodes berechnen...
Pruefen ob jeder Code zyklisch ist...
Zyklen erstellen...
Code 1986 wird nach 1560d wiederholt.
Es gibt 12 Zyklen.
Zyklus 0: len 1, 1. Code 0000
Zyklus 1: len 1560, 1. Code 0001
Zyklus 2: len 312, 1. Code 0002
Zyklus 3: len 5, 1. Code 0005
Zyklus 4: len 1560, 1. Code 0010
Zyklus 5: len 1560, 1. Code 0012
Zyklus 6: len 1560, 1. Code 0015
Zyklus 7: len 312, 1. Code 0020
Zyklus 8: len 5, 1. Code 0050
Zyklus 9: len 1560, 1. Code 0111
Zyklus 10: len 1560, 1. Code 0113
Zyklus 11: len 5, 1. Code 0555
Laufzeit: 56983ms
ready.[/code]
Der Speicher ist ganz gut ausgenutzt. Von den ca. 50 Kilobyte die für Programm und Daten zur Verfügung stehen sind nur noch ca. 6 Kilobyte frei.
[codebox=c file=Unbenannt.c]#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define CODE_COUNT 10000
#define MAX_CYCLE_COUNT 100
typedef struct
{
uint16_t next_code;
uint8_t cycle_index;
} CodeInfo;
typedef struct
{
uint16_t first_code;
uint16_t length;
} Cycle;
typedef struct
{
uint8_t length;
Cycle items[MAX_CYCLE_COUNT];
} Cycles;
static CodeInfo code_infos[CODE_COUNT];
static Cycles cycles;
uint8_t cross_sum(uint16_t code)
{
uint8_t sum = 0;
div_t tmp;
while (code) {
tmp = div(code, 10);
code = tmp.quot;
sum += tmp.rem;
}
return sum;
}
void code_infos_init(void)
{
register uint16_t code;
register CodeInfo *info;
for (info = code_infos, code = 0; code < CODE_COUNT; ++info, ++code)
{
info->next_code = code % (CODE_COUNT / 10) * 10 + cross_sum(code) % 10;
info->cycle_index = 0xff;
}
}
bool has_just_cycles(void)
{
register uint16_t code;
register bool *has_incoming;
bool code_has_incoming[CODE_COUNT];
memset(code_has_incoming, false, sizeof(code_has_incoming));
for (code = 0; code < CODE_COUNT; ++code)
{
has_incoming = &code_has_incoming[code_infos
Code: Alles auswählen
.next_code];
if (*has_incoming) return false;
*has_incoming = true;
}
for (
has_incoming = code_has_incoming, code = 0;
code < CODE_COUNT;
++has_incoming, ++code
) {
if (!*has_incoming) return false;
}
return true;
}
void create_cycles(void)
{
register uint16_t code;
register CodeInfo *info;
register Cycle *cycle;
register uint16_t start_code;
cycles.length = 0;
for (start_code = 0; start_code < CODE_COUNT; ++start_code)
{
if (code_infos[start_code].cycle_index == 0xff) {
cycle = &cycles.items[cycles.length];
cycle->first_code = code = start_code;
cycle->length = 0;
do {
++cycle->length;
info = &code_infos[code];
info->cycle_index = cycles.length;
code = info->next_code;
} while (code != start_code);
++cycles.length;
if (cycles.length == MAX_CYCLE_COUNT) {
printf("Mehr als %d Zyklen!\n", MAX_CYCLE_COUNT);
exit(1);
}
}
}
}
void print_code_and_day_count(uint16_t code)
{
printf(
"Code %04d wird nach %dd wiederholt.\n",
code,
cycles.items[code_infos[code].cycle_index].length
);
}
void print_cycles_info(void)
{
uint8_t i;
printf("Es gibt %d Zyklen.\n", cycles.length);
for (i = 0; i < cycles.length; ++i)
{
printf(
"Zyklus %3d: len %4d, 1. Code %04d\n",
i,
cycles.items[i].length,
cycles.items[i].first_code
);
}
}
int main(void)
{
clock_t start_time = clock();
clock_t end_time;
puts("Folgecodes berechnen...");
code_infos_init();
puts("Pruefen ob jeder Code zyklisch ist...");
if (!has_just_cycles()) {
puts("Es gibt Codes die nie wieder erreicht\nwerden.");
return 1;
}
puts("Zyklen erstellen...");
create_cycles();
end_time = clock();
print_code_and_day_count(1986);
print_cycles_info();
printf("Laufzeit: %ldms\n", (end_time - start_time) * 1000 / CLOCKS_PER_SEC);
return 0;
}