Dwumiany - SPOJ

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ź.

#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;
}

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

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ę.

Niby-rozwiązanie: https://wandbox.org/permlink/2IQnwlQdaCrK83Xp

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

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.

https://www.matematyka.pl/56229.htm#p221748

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.

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

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;
	}
}

vpiotr napisał(a):

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

https://softwareengineering.stackexchange.com/questions/320247/has-can-anyone-challenge-uncle-bob-on-his-love-of-removing-useless-braces

https://softwareengineering.stackexchange.com/questions/16528/single-statement-if-block-braces-or-no

Wiele ciekawych argumentów przeciwko temu dogmatowi. "Sam" Uncle Bob uważa, żeby klamerki usuwać.