Toto vlákno bylo označeno za vyřešené.
crazy ~ Moderátor
+10
Grafoman
Zdravím,
už nad tím přemýšlím docela dlouho a zatím mě nenapadlo jak z prvočíselného rozkladu určit součet všech dělitelů čísla. Vím, že je spolu musím nějak vynásobit, atp. Například pro číslo 20 - prvočíselný rozklad je 2*2*5 a já z toho potřebuji dostat součet dělitelů, čili: 1+2+4+5+10=22. Za každý nápad díky
All you need is vision and time.
crazy ~ Moderátor
+10
Grafoman
Opravdu nevíte? Moc by mi to pomohlo...
All you need is vision and time.
Tady jsem zbastlil kód který ti třeba pomůže, ale rychlost nic moc :-)
(Princip je asi takový, že se postupně k součtu rekurzivně přičítají všechny kombinace prvků rozkladu)
#include <stdio.h>
#include <assert.h>
#include <string.h>
#define DELKA_ROZKLADU (sizeof(prvociselnyRozklad) / sizeof(prvociselnyRozklad[0]))
int prvociselnyRozklad[] = {2, 2, 5}; // Cisla v rozkladu musi byt serazena vzestupne
struct BLOCK {
int* mocniny;
int powCount;
};
BLOCK blocks[DELKA_ROZKLADU];
int blocksCount = 0;
void InitBlocks();
void PrintBlocks();
int RecursiveSum(int start, int mul); // Pozor: hloubka rekurze = pocet mocnin v rozkladu + 1 (např pro 2^4 * 5 je hloubka = 3)
int main(int argc, char* argv[])
{
int slozeneCislo = 1;
for (int j = 0; j < DELKA_ROZKLADU; j++) {
slozeneCislo *= prvociselnyRozklad[j];
}
InitBlocks(); // Prevede jednotlive prvky v rozkladu na mocniny (napr 2, 2, 2, 3, 3, 5 na 2^3, 3^2, 5)
PrintBlocks();
int sum = 1 + RecursiveSum(0, 1) - slozeneCislo;
printf("Soucet delitelu: %d\n", sum);
return 0;
}
void InitBlocks()
{
blocksCount = 0;
blocks[blocksCount].powCount = 1;
blocks[blocksCount].mocniny = prvociselnyRozklad;
int j = 1;
while (j < DELKA_ROZKLADU) {
if (prvociselnyRozklad[j] != blocks[blocksCount].mocniny[0]) {
blocksCount++;
blocks[blocksCount].powCount = 1;
blocks[blocksCount].mocniny = prvociselnyRozklad + j;
} else {
prvociselnyRozklad[j] *= prvociselnyRozklad[j - 1];
blocks[blocksCount].powCount++;
}
j++;
}
blocksCount++;
}
void PrintBlocks()
{
for (int j = 0; j < blocksCount; j++) {
if (blocks[j].powCount == 1) {
printf("%d", blocks[j].mocniny[0]);
} else {
printf("%d^%d", blocks[j].mocniny[0], blocks[j].powCount);
}
if (j < blocksCount - 1) {
printf(" * ");
}
}
printf("\n");
}
int RecursiveSum(int start, int mul)
{
int sum = 0;
for (int blockIndex = start; blockIndex < blocksCount; blockIndex++) {
for (int powIndex = 0; powIndex < blocks[blockIndex].powCount; powIndex++) {
const int m = mul * blocks[blockIndex].mocniny[powIndex];
sum += m + RecursiveSum(blockIndex + 1, m);
}
}
return sum;
}
crazy ~ Moderátor
+10
Grafoman
All you need is vision and time.
Zjistit počet nových příspěvků
Přidej příspěvek
Uživatelé prohlížející si toto vlákno Uživatelé on-line: 0 registrovaných, 1 host