Súčet všetkých podreťazcov reprezentujúcich čísla – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Súčet všetkých podreťazcov reprezentujúcich čísla – C / C++ – Fórum – Programujte.comSúčet všetkých podreťazcov reprezentujúcich čísla – C / C++ – Fórum – Programujte.com

 

Spuštěný nový filmový web Filmožrouti.cz — vše o Avengers, Pacific Rim, Thor, Star Wars…
Jozef010
Newbie
20. 5. 2018   #1
-
0
-

Zdravím, mohol by mi niekto, prosím vysvetliť, ako funguje tento kód na zistenie súčtu čísel zo všetkých podreťazcov vstupného reťazca. (1234=1+2+3+4+12+23+34+123+234+1234)

 Malo by to mať niečo spoločné s dynamickým programovaním, ale neviem, ako to funguje.

#include <bits/stdc++.h>
using namespace std;
 
// Utility method to covert character digit to
// integer digit
int toDigit(char ch)
{
    return (ch - '0');
}
 
// Returns sum of all substring of num
int sumOfSubstrings(string num)
{
    int n = num.length();
 
    //  allocate memory equal to length of string
    int sumofdigit[n];
 
    //  initialize first value with first digit
    sumofdigit[0] = toDigit(num[0]);
    int res = sumofdigit[0];
 
    //  loop over all digits of string
    for (int i=1; i<n; i++)
    {
        int numi = toDigit(num[i]);
 
        // update each sumofdigit from previous value
        sumofdigit[i] = (i+1) * numi +
                        10 * sumofdigit[i-1];
 
        // add current value to the result
        res += sumofdigit[i];
    }
 
    return res;
}
 
//  Driver code to test above methods
int main()
{
    string num = "1234";
    cout << sumOfSubstrings(num) << endl;
    return 0;
}

Ďakujem za odpoveď

Nahlásit jako SPAM
IP: 212.5.196.–
gna
~ Anonymní uživatel
653 příspěvků
20. 5. 2018   #2
-
0
-

To se dost špatně vysvětluje. Zkus ten výpočet rozložit a uvidíš to. První část je

(i+1) * numi

To je vidět hned 

1 + 2 + 3 + 4  +  12 + 23 + 34        +  123 + 234            +  1234
1 + 2 + 3 + 4  +  10+2 + 20+3 + 30+4  +  120+3 + 230+4        +  1230+4
1 + 2 + 3 + 4  +  10+2 + 20+3 + 30+4  +  100+20+3 + 200+30+4  +  1000+200+30+4
1              +  10 + 20 + 30        +  100+20 + 200+30      +  1000+200+30    +  2*2 + 3*3 + 4*4

Další část

10 * sumofdigit[i-1]

Když si s tím pohraješ, tak je vidět, že v každém kroku je řádový posun předchozího.

1   +   10 + 2*2   +   100 + 2*2*10 + 3*3   +   1000 + 2*2*100 + 3*3*10 + 4*4
1   +   10 + 2*2   +   (10+2*2)*10  + 3*3   +   ((10+2*2)*10 + 3*3)*10  + 4*4
Nahlásit jako SPAM
IP: 213.211.51.–
Zjistit počet nových příspěvků

Přidej příspěvek

×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, 36 hostů

Moderátoři diskuze

 

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