Dwumiany - SPOJ

SI
  • Rejestracja:ponad 7 lat
  • Ostatnio:ponad rok
  • Postów:61
0

Robię sobie zadanko na SPOJa - Dwumiany. Wydaje mi się, że w tym kodzie jest wszystko dobrze, dla wszystkich liczb gdzie wynik jest mniejszy niż 1 000 000 000 jest w porządku. Proszę o podpowiedź.

Kopiuj
#include <iostream>
#include <iomanip>

using namespace std;

int t, liczbaA, liczbaB;

int main()
{
    cin >> t;
    for(int i=1; i<=t;i++)
    {
        cin >> liczbaA >> liczbaB;
        long double silniaA=1;
        long double silniaB=1;
        long double silniaC=1;
        if(liczbaA==0) silniaA=1;
        else
        {
            for (int j=1; j<=liczbaA;j++)
            {
                silniaA = silniaA * j;
            }
        }
        if(liczbaB==0) silniaB=1;
        else
        {
            for (int k=1; k<=liczbaB;k++)
            {
                silniaB = silniaB * k;
            }
        }
        if ((liczbaA==0) && (liczbaB == 0))silniaC=1;
        else
        {
           for (int l=1; l<=liczbaA-liczbaB;l++)
            {
                silniaC = silniaC * l;
            }
        }

        long double wynik = silniaA/(silniaB*silniaC);
        cout << setprecision(10000);
        cout << wynik << endl;
    }

    return 0;
}
edytowany 1x, ostatnio: kq
vpiotr
  • Rejestracja:ponad 13 lat
  • Ostatnio:prawie 3 lata
0

Podpowiedź: używaj klamerek w if i else.

SI
kq
Moderator C/C++
  • Rejestracja:prawie 12 lat
  • Ostatnio:około 12 godzin
  • Lokalizacja:Szczecin
1

Wyniki pośrednie wychodzą poza zakres dokładności (poza tym, po kiego dla wyników całkowitych double?!). Np. dla 500 499 spodziewany wynik to 500, a Twój kod zwraca 499.9999 i jakieś cyferki

Znasz to powiedzenie, że programista miał problem, postanowił użyć liczb zmiennoprzecinkowych do jego rozwiązania i teraz miał 2.000000000000000000000002 problemy? Polecam lekturę.


kq
PS: @kaczus https pls ;​)
vpiotr
  • Rejestracja:ponad 13 lat
  • Ostatnio:prawie 3 lata
0
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:4 minuty
  • Postów:4927
0

Wychodza poza zakres, bo tak prosto policzyc sie nie da, trzeba sie przyjrzec temu wzorowi pomyslec co dalej.


MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:4 minuty
0

Weź rozpisz sobie symbol newtona tak by zminimalizować liczbę mnożeń. Wtedy dostaniesz przepis na dwumian, w którym nie musisz liczyć silni (tylko jej kawałek). Dzięki temu nie przekroczysz zakresu int.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
vpiotr
  • Rejestracja:ponad 13 lat
  • Ostatnio:prawie 3 lata
0
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:4 minuty
  • Postów:4927
0
MarekR22 napisał(a):

Weź rozpisz sobie symbol newtona tak by zminimalizować liczbę mnożeń. Wtedy dostaniesz przepis na dwumian, w którym nie musisz liczyć silni (tylko jej kawałek). Dzięki temu nie przekroczysz zakresu int.

Nawet to chyba nie wystarczy.


kq
Moderator C/C++
  • Rejestracja:prawie 12 lat
  • Ostatnio:około 12 godzin
  • Lokalizacja:Szczecin
0

Wystarczy, moje rozwiązanie tego zadania w D z tego korzysta:

Kopiuj
import std.algorithm;
import std.bigint;
import std.conv;
import std.format;
import std.functional;
import std.math;
import std.stdio;
import std.string;


auto binomialCoefficientImpl(T,U)(U k, U n)
{
	T result = 1;
	auto loopMax = min(k-n, n);
	for(U i = 0; i < loopMax; ++i){
		result *= k-i;
		result /= i+1;
	}
	return result;
}

alias binomialCoefficient = memoize!(binomialCoefficientImpl!(ulong, uint));

auto extract(T, R)(R r)
{
	T t;
	if(r.readf(" %s", &t) != 1){
		throw new Error("readf failed");
	}
	//"extracted: '%s'".format(t).writeln;
	return t;
}

void main()
{
	int numberOfTests = stdin.extract!uint;
	for(int i = 0; i < numberOfTests; ++i) {
		int k, n;
		k = stdin.extract!uint;
		n = stdin.extract!uint;
		binomialCoefficient(k, n).writeln;
	}
}

KM
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 4 lata
  • Postów:473
0
Zobacz pozostałe 22 komentarze
KM
Przykład. A poza tym, jest wiele sposobów, by prawdopodobienstwo takiego błędu radykalnie zmiejszyć: -Wmisleading-indendation, autoindent w IDE, etc, etc.
WeiXiao
No przecież ten przykład z bugiem appla był już tutaj linkowany.
KM
i...?
WeiXiao
no chciałeś przykład, to ci podałem :P
KM
No to ja podkreślam, że to jest tylko "przykład". Ja też mogę podać przykład na to, że idąc ulicą komuś cegła spadła na głowę i umarł na miejscu, ale to jeszcze nie powód, by nie ruszać się z domu bez pancernego parasola :)

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.