Prvočíselný rozklad na součet dělitelů – Matematika – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Prvočíselný rozklad na součet dělitelů – Matematika – Fórum – Programujte.comPrvočíselný rozklad na součet dělitelů – Matematika – Fórum – Programujte.com

 

Toto vlákno bylo označeno za vyřešené.
crazy
~ Moderátor
+10
Grafoman
29. 10. 2011   #1
-
0
-

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

Nahlásit jako SPAM
IP: 89.190.90.–
All you need is vision and time.
crazy
~ Moderátor
+10
Grafoman
30. 10. 2011   #2
-
0
-

Opravdu nevíte? Moc by mi to pomohlo...

Nahlásit jako SPAM
IP: 89.190.90.–
All you need is vision and time.
Pudni tvor+2
Stálý člen
30. 10. 2011   #3
-
0
-

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;
}
Nahlásit jako SPAM
IP: 90.180.213.–
crazy
~ Moderátor
+10
Grafoman
30. 10. 2011   #4
-
0
-
Nahlásit jako SPAM
IP: 89.190.90.–
All you need is vision and time.
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 1 host

Podobná vlákna

Prvočíselný roklad — založil mima115

Pocet delitelu — založil Neox

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý