Potrzebna pomoc przy rzyspieszeniu pracy funkcji matematycznej w programach

Question

Mam dwa programy do wyliczania ktore dzialaja tylko dla malych liczb gdy wrzucam porgramy na strone wywala mi blad o przekroczeniu czasu wykonywania programu

 

1 Program do wyznaczania 1*2^2 + 2*3^2 + ... + n(n+1)^2 na wejscie dajemy np 1 2 (gdzie 1 oznacza ilosc liczb ktore trzeba wstawic do wzoru (zawsze jest to 1 liczba) a w ta liczbe)

#include <iostream>
#include<math.h>

using namespace std;

int main()
{
          {

            int n,i,jeden;
            long long x=0;

    cin>>jeden>>n;

    for (i = 1; i <= n; i++)
    {
        x=(x+(i*(pow((i+1),2))));

}
   cout<<x<<" ";

        }
}

Nie wyrabia sie w czasie dla duzego n

 

2 Program do zliczania bitow 1 w danej liczbie na wejscie dajemy np 2 3 4 (2 oznacza iosc liczb a 3 i 4 liczby do przeliczenia)

#include <iostream>
#include<math.h>

using namespace std;

int main()
      {


        int test,liczba;
            cin >> test;

    for(int i=0; i<test; i++)
    {
        cin >> liczba;

        for (int i=2; i<=liczba; i++)
        {
            if (liczba%i==0)
                {
                if (i==liczba) cout<<"1"<<" ";
                else cout<<"0"<<" ";
                break;
            }

        }

 }

     }

Nie wyrabia sie dla duzej lizcby

Comments

Podaj polecenia tych zadań...

---

dla 1

Wyznacz wartość wyrażenia 1*2^2 + 2*3^2 + ... + n(n+1)^2 dla zadanego n.

 

dla 2

 Zlicz liczbę ustawionych bitów w liczbie naturalnej (unsigned).

---

https://en.wikipedia.org/wiki/Hamming_weight

Pierwsze pewnie da się obliczyć z jakiejś zależność.

---

@BloodyBoy89,  w drugim zadaniu masz obliczyć ilość zapalonych bitów, a nie konwertować liczbę do postaci binarnej.

unsigned int v = 666; // przykładowa liczba
int sum = 0;
    
while (v > 0) {
    if (v & 1) ++sum;
    v >>= 1;
}

Wydaje mi się, że to zadanie było już w tym tygodniu na tym forum...

Answer 1

W pierwszym programie możesz użyć rekurencji, czyli funkcja ma wywoływać samą siebie w celu zwrócenia prawidłowego wyniku. Zauważ, że gdyby funkcja obliczała tylko jedną część całego dodawania (np. 2*3^2, lub 1*2^2), a jej parametrem byłaby liczba n, oznaczającą, ostatnią część dodawania, to wtedy oblicz(4), byłoby równe oblicz(3) + 4*5^4

 

Jeśli nie będziesz mógł sobie poradzić, napisz. Chętnie pomogę :)

Comments

http://quick-bench.com/xSF5cdJk7h8rCuH85SCVyvHhv3k

---

@tkz, błędnie zaimplementowałeś wersję rekurencyjną - potęgowanie jest zawsze do kwadratu, a Ty dałeś do N.

 

Tu z moją wersją zwykla2 -> http://quick-bench.com/-lwtGOGpH2Qr55UxJvygYg8bjEM

---

Fakt, moje przeoczenie, co nie zmienia faktu, że wersja rekurencyjna jest i tak wolniejsza. Szczególnie od Twojej implementacji, bo aż 9 razy.