C :: Aufgabe #50
2 Lösungen
Austarieren (Mathematisches Problem)
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
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
Lösungen:
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;
}
C-Code#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> coeffs;
cout << "n: ";
int n;
cin >> n;
int tmp = n;
while (tmp > 1) {
switch (tmp % 3) {
case 0: coeffs.push_back(0); break;
case 1: coeffs.push_back(1); break;
case 2: coeffs.push_back(-1); tmp++; break;
}
tmp /= 3;
}
coeffs.push_back(1);
cout << "n = " << n << endl;
cout << "m = " << (coeffs.size() - 1) << endl;
cout << n << " =" << endl;
for (int i = coeffs.size() - 1; i >= 0; i--)
{
if (coeffs[i] == 1)
cout << "+3**" << i << endl;
else if (coeffs[i] == -1)
cout << "-3**" << i << endl;
}
}