C#: Hvordan multiplisere 100! i C#?

[hoyre]

Hei!

 

Prøver å mulitplisere 100! i C#, altså 100*99*98*97.....*1, men skjønner ikke hvorfor jeg får null som svar:

 

       long fac = 1;

       for (int i = 2; i <= 100; i++)
       {
           fac = fac * i;
       }
       labSum.Text = "Den totale summen er " + fac;

 

 

Hva gjøres feil her?

Endret 13. januar 2012 av hoyre

[MailMan13]

Int64 / long kan bare representere opp til 2^63-1. 100! er mye større enn det.

 

Sleng inn en referanse til System.Numerics, og bruk BigInteger i stedet. Den har arbirtær størrelse.

[Eplenektar1]

red: folk er raskere enn meg.

Endret 13. januar 2012 av Eplenektar1

[hoyre]

Int64 / long kan bare representere opp til 2^63-1. 100! er mye større enn det.

 

Sleng inn en referanse til System.Numerics, og bruk BigInteger i stedet. Den har arbirtær størrelse.

 

 

Dette var nytt! Har bare brukt int og long for heltallsverdier, så ser ikke hvordan jeg skal gå fram med en BigInteger.

[srbz]

BigInteger er en objekttype beskrevet i programmeringsspråkets bibliotek.

 

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx

 

Jeg kan ikke C#, men det vil nok ligne veldig på en tilsvarende løsning i Java:

	public static BigInteger fac(int i){
	if(i == 1)
		return new BigInteger("1");
	if(i < 1)
		return new BigInteger("0");

	BigInteger f = new BigInteger("1");
	for(int j = 2; j <= i; j++){
		f = f.multiply(new BigInteger(""+j));
	}
	return f;
}

Dette er da en metode som vil returnere i!. Istedenfor å operere direkte med verdier (int, long, float, double) opererer du med objekter som innehar den tilsvarende verdien. (I Java kan ikke BigInteger ta int som argument, derfor parser jeg til String på linje 9). Kanskje ikke den mest elegante løsningen, men den virker.

 

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

( ~ 9,33 * 10^157 )

 

edit: For ordens skyld, uttrykket

f = f.multiply(new BigInteger(""+j));

ville vært ekvivalent med uttrykket

f = f * j;

alternativt

f *= j;

dersom variabelen f var eksempelvis int eller long. Det som skjer på linje 9 er altså egentlig akkurat det samme som skjer inni din egen for-løkke, bare at tallene multipliseres ved hjelp av BigInteger istedenfor int eller long.

Endret 13. januar 2012 av srbz

[MailMan13]

BigInteger implementerer alle de vanlige operatorene, inkudert implisit widening conversion fra de andre heltallstypene. Eneste som skal endre seg i koden deklarasjonen av variabelen.

 

- Sett inn en referanse til "System.Numerics" (Add Reference i visual studio, så finenr du den på .Net-tabben der).

- Inkluder namespacet System.Numerics på toppen

- endre "long" til "BigInteger"

Endret 13. januar 2012 av MailMan13

[hoyre]

BigInteger implementerer alle de vanlige operatorene, inkudert implisit widening conversion fra de andre heltallstypene. Eneste som skal endre seg i koden deklarasjonen av variabelen.

 

- Sett inn en referanse til "System.Numerics" (Add Reference i visual studio, så finenr du den på .Net-tabben der).

- Inkluder namespacet System.Numerics på toppen

- endre "long" til "BigInteger"

 

Problemet er at i visual web, så finner jeg ingen system.numeric under .NET

[Wattengård]

Den er en del av .NET 4.0 ... har du oppgradert?

[wolf5]

Eller du kan gjøre det helt basic. Gange slik du lærte på skolen. 1 og 1 tall ganget med 100, 99, 98 osv og plusse sammen til slutt, men du må forholde deg til tallene i en array. Moro greie å prøve ut.

[wolf5]

Og for moro skyld blir den varianten ganske så enkel:

 

           var tall = new int[1000]; //Listen av alle tallene vi skal ende opp med som svar
           tall[0] = 1; //initiell verdi 

           for (int multiplier = 1; multiplier <= 100; multiplier++) {
               int mente = 0;
               for (int i = 0; i < tall.Length; i++) {
                   int verdi = (tall[i] * multiplier) + mente;
                   tall[i] = verdi % 10;
                   mente = verdi / 10;
               }
           }
           string sum = "";
           for (int i = tall.Length - 1; i >= 0; i--) {
               sum += tall[i].ToString();
           }

           Debug.WriteLine(sum.TrimStart('0'));

 

---> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

[GeirGrusom]

var result = Enumerable.Range(1, 100).Aggregate<int, BigInteger>(BigInteger.One, (a, b) => a * b);

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Endret 15. januar 2012 av GeirGrusom

[wolf5]

Eller for de som ikke benytter 4.0 av .Net og liker leselig kode:

 

var result = Enumerable.Range(1, 100).Aggregate<int, List<int>>(new List<int>(new int[158]), (tall, multiplier) => { int mente = 0; for (int i = 0; i < tall.Count; i++) { int verdi = (((i == 0 && multiplier == 1) ? 1 : tall[i]) * multiplier) + mente; tall[i] = verdi % 10; mente = verdi / 10; } return tall; }).ConvertAll<string>(d => d.ToString()).Aggregate((a, b) => (b + a));

 

[MailMan13]

Func<int, BigInteger> f = null;
f = x => x <= 1 ? x : x * f(x - 1);

Console.WriteLine(f(100));

Endret 16. januar 2012 av MailMan13

[GeirGrusom]

Func<int, BigInteger> f = null;
f = x => x <= 1 ? x : x * f(x - 1);

Console.WriteLine(f(100));

f(0) skal være 1

 

Er forøvrig C# implementasjonen tail-call optimalisert?

Endret 16. januar 2012 av GeirGrusom

[MailMan13]

Mener den skal kunne det. Er ihvertfall en egen opcode for det i IL (.tail), så er det vel op til JIT å finne ut om det er fornuftig.

Endret 16. januar 2012 av MailMan13

[snippsat]

Eller for de som ikke benytter 4.0 av .Net og liker leselig kode:

Så du mener at en line på 378 tegn skal være leselig

Liker nok GeirGrusom og MailMan13 sine eksempler bedere.

Litt python 28 tegn som litt midere og gå igjennom enn 378 tegn.

>>> f=lambda x:+(x<2)or x*f(x-1)
>>> f(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

[wolf5]

Ironisk ment, men hvor .Net 4.0 ikke er kravet.