Austarieren (Mathematisches Problem)

C :: Aufgabe #50 :: Lösung #1

2 Lösungen

#50

Anfänger - C von bibir - 03.09.2014 um 08:27 Uhr

Der folgenden Aufgabenstellung liegt das Problem des Austarierens zugrunde, wie man es z. B. bei einer Balkenwaage mit einer vorgegebenen Anzahl von Gewichten vorfindet.
Jede natürliche Zahl n lässt sich als Summe von Potenzen zur Basis 3 eindeutig darstellen.

Die Eindeutigkeit dieser Darstellung soll als gesichert vorausgesetzt werden.

Es ist ein Programm/Skript zu schreiben, das zu einer einzulesenden Zahl n <= 2000 den Wert m und die
Koeffizienten berechnet. Die Ausgabe soll wie im Beispiel angegeben erfolgen.

Hinweis: Das m ist gleich dem größten j, für das gilt: 3j < 2n.

Beispiel:
Für n = 46 erhält man m = 4.
Die Ausgabe sieht dann folgendermaßen aus:
n = 46
m = 4
46 =
+3**4
-3**3
-3**2
+3**0

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von devnull (8870 Punkte) - 20.09.2014 um 18:31 Uhr

C-Code

/***********************************
 * tarieren.c   Austarieren
 ***********************************/
#include <stdlib.h>
#include <stdio.h>

// Global array
long apw3[50];
 
// Potenz zur Basis 3 berechnen 
unsigned long power3(int exp) {
	long p = 1;
	int e;
	for (e=0; e<exp; e++)
		p *= 3L;
	return p;
}

// Potenzen zur Basis 3 berechnen und 
// den maximalen Exponenten bestimmen
int calc_powers(long N) {	   
	int m = 0;
    while ((apw3[m] = power3(m)) < 2*N)
		m++;
	return m-1;		
}
	
// Die Potenzreihe rekursiv berechnen
// Returncode 1: Potenzsumme == Zahl
int calc_powsum(long N, int e, long sum) {
	long pw;

	// Abbruchbedingung der Rekursion
	if (e < 0) {
		if (N == sum) {
			printf("%ld =", N);
			return 1;
		}
		return 0;
	}
	pw = apw3[e];
	// Vorzeichen Minus
	if (calc_powsum(N, e-1, sum-pw)) {
		printf(" - 3**%d", e);
		return 1;
	}
	// kein Beitrag zur Summe
	if (calc_powsum(N, e-1, sum))
		return 1;
	// Vorzeichen Plus
	if (calc_powsum(N, e-1, sum+pw)) {
		printf(" + 3**%d", e);
		return 1;
	}
	return 0;
}

// main	   
int main(int argc, char **argv) {
	long N;
	
    if (argc > 1)
        N = atol(argv[1]);
    else {
        printf("Eingabe Zahl: ");
        scanf("%ld", &N);
    }
	calc_powsum(N, calc_powers(N), 0);
	printf("\n");
    return 0;
}