suma silni - pomoc w zadaniu

0

Napisz program, który wczytuje ze standardowego wejścia nieujemną liczbę całkowitą n i wypisuje na standardowym wyjściu wartość 0! + 1! + … + n!.
Wydukałem coś takiego, ale chodzi o coś innego. Jakaś wskazówka jak rozwiązać to zadanie?

#include <iostream>
using namespace std;

int silnia(int n) {

	int silnia = 1;

	for (int i = 1; i <= n; i++) {
		silnia *= i;
		return silnia;
	}

}
int main() {
	int n;
	int suma = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
		suma += silnia(i);

	cout << suma << endl;

	return 0;
}
4
    for (int i = 1; i <= n; i++) {
        silnia *= i;
        return silnia;
    }

Jak myślisz, czy pętla kontynuuje po wyjściu z funkcji?

Swoją drogą, to Twoje rozwiązanie jest O(n²), to zadanie spokojnie można policzyć w O(n).

0

tak wiem że ta pętla wykona się raz, ale próbowałem to zmieniać i wkleiłem po prostu pierwszą wersje tego co napisałem. nie mam pomysłu jak to zrobić

0

zrobilem jeszcze cos takiego tylko nie dodaje mi 0! do sumy, czy jesli zrobie po prostu cout<<suma+1<<endl; to będzie to poprawnie czy jest inny sposob?

#include <iostream>
using namespace std;


int main() {
int n;
int silnia=1;
int suma = 0;
cin >> n;

for (int i = 1; i <= n; i++) {
	
	silnia *= i;
	suma += silnia;
}
cout << suma << endl;

return 0;
}
1

Jest jakieś ograniczneie na to n, bo silnia, to jednak dość szybko rośnie...

0

musisz zacząć pętle od zera

oraz silnię trza zmienić, np tak:

unsigned long long silnia(unsigned n) 
{
	unsigned long long ret=1;
	while(n>1) ret*=n--;
	return ret;
}
1

Tak jak napisał @kq, pomyśl o rozwiązaniu o złożoności obliczeniowej O(n).

Zauważ, że jeżeli 1! + 2! + 3! + 4! + 5! zapisze się w taki sposób:

1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + 1 * 2 * 3 * 4 * 5

To po wyciągnięciu wspólnych czynników przed nawias otrzymuje się taki zapis:

1 * (1 + 2 * (1 + 3 * (1 + 4 * (1 + 5))))

Można zaimplementować kod, który oblicza wynik w sposób iteracyjny i rekurencyjny na zasadziej podobnej do obliczania silni. W moim rozwiązaniu rekurencyjnym musiałem wprowadzić dodatkowy wejściowy parametr, który ma wartość domyślną 1, a w każdym kolejnym wywołaniu inkrementuje się, aż osiągnie wartość n.

0

Nie wiem o co chodzi, przecież on to chyba dobrze napisał powyżej, dodałem jeszcze , w oczywisty sposób poprawną funkcję rekurencyjną, do przetestowania:

long sumFactorialsDigits(long n) {
	long sum = 1;
	long fact = 1;
	long i = 1;
	while ( i <= n){
		fact *= i;
		sum += fact;
		++i;
	}
	return sum;
}

long factorial(long n) {
	if (n == 0) return 1;
	else return n * factorial(n - 1);
}

long sumFactorialsDigitsRec(long n) {
	if (n == 0) return 1;
	else return factorial(n) + sumFactorialsDigitsRec(n - 1);
}

int main(int argc, char **argv){		
	long a = 5, b = 6;
	cout << (sumFactorialsDigits(a) == sumFactorialsDigitsRec(a)) <<endl; // -> 1
	cout << (sumFactorialsDigits(b) == sumFactorialsDigitsRec(b)) <<endl; // -> 1
	cout << sumFactorialsDigitsRec(3) <<endl; // -> 10
	cout << sumFactorialsDigits(a) <<endl; 
	cout << sumFactorialsDigits(b) <<endl;
	cout << "\n";
	return 0;
}
0
Burmistrz napisał(a):

Tak jak napisał @kq, pomyśl o rozwiązaniu o złożoności obliczeniowej O(n).

Zauważ, że jeżeli 1! + 2! + 3! + 4! + 5! zapisze się w taki sposób:

1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + 1 * 2 * 3 * 4 * 5

To po wyciągnięciu wspólnych czynników przed nawias otrzymuje się taki zapis:

1 * (1 + 2 * (1 + 3 * (1 + 4 * (1 + 5))))

Można zaimplementować kod, który oblicza wynik w sposób iteracyjny i rekurencyjny na zasadziej podobnej do obliczania silni. W moim rozwiązaniu rekurencyjnym musiałem wprowadzić dodatkowy wejściowy parametr, który ma wartość domyślną 1, a w każdym kolejnym wywołaniu inkrementuje się, aż osiągnie wartość n.

unsigned long long sum_silnia(unsigned n) 
{
    unsigned long long ret=1,s=1;
    for(unsigned long long i=1;i<=n;++i) ret+=(s*=i);
    return ret;
}

Ja tu nie widzę O(n^2), nie widzę powodów przekształcać - jedynie kod zaciemni.

1

Te rozwiazania powyzej sa dobre, ale w obecnej postaci to tak banalny problem, ze mozna to rozwiazac bez komputera (na kartce - dla liczb 64 bit to jest maks 20 mnozen i dodawan).
Proponuje kilka rozszerzen zadania:

  1. Dodaj sprawdzenie czy w ogole jest sens liczyc wartosc, silnia bardzo szybko wyskakuje poza zakres long czy int.

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

  1. Dodaj policzenie wg aproksymacji dla za duzych liczb

  2. Sprobuj zaimplementowac swoj wlasny typ numeryczny o zmiennej precyzji, gdzie kazda cyfra jest trzymana w osobnym elemencie tablicy.

  3. Zastosuj liczby o konfigurowalnej podstawie, np 256.

2

Jako, że silnia rożnie bardzo bardzo szybko, to zakres int skończy ci się już dla małej wartości n.
Teraz jeśli masz gwarancję, że wynik zmieści się w int (n nie przekroczy jakiejś wartości), to najbardziej prostym rozwiązanie jest stabilizować wszystkie możliwe wyniki (jest ich mało).

Jeśli nie ma takiego ograniczania na n to długa droga przed tobą, bo musisz zaimplementować arytmetykę dużych liczb.

1 użytkowników online, w tym zalogowanych: 0, gości: 1