Trädvy Permalänk
Medlem
Registrerad
Okt 2012

Multiplisera i en for loop.

Okej, skall skriva ett program som behöver multiplicera tal med varandra i en forloop.
Tex om användaren matar in ett värde av 5 skall programmet skriva ut 5 * 4 * 3 * 2 * 1 = .....( sry orkade inte räkna ut )

for (int i = x; i > 0; i--) { }

hade tänkt att använda mig av denna som bas och fortsätta från där men oavsätt vad jag skriver in så gångrar den fel tal.

tacksam för all hjälp jag kan få.

dator: Intel Core i5 3570K | Noctua NH-D14 | MSI Z77A-GD65 ATX | Corsair 16GB 1600MHz VENGEANCE LP | XFX Core Edition 850W 80+ Bronze | Corsair Carbide 500R | Sapphire Radeon HD 7970 GHz 3GB | Samsung SSD 840 Series 250GB | 2st. 2TB Seagate Barracuda 7200rpm SATA 6Gbit/s | DVD±RW Samsung 24X DL
Kringutrustning: ASUS MX279H 27" | Microsoft sidewinder x4 | Func MS-3 v2

Trädvy Permalänk
Medlem
Plats
Arboga
Registrerad
Jan 2002

var res = 1; for (int i = x; i > 0; i--) { res *= i; }

Nåt i den stilen borde fungera

Skickades från m.sweclockers.com

Intel Core i7 6700K | Gigabyte Z170X-UD3 | Corsair Vengeance LPX 16GB DDR4 2400Mhz | EVGA GTX 980Ti Hybrid | Samsung 950 PRO 256GB | Noctua NH-D15 | EVGA G2 750 | Fractal Design Define R5

Trädvy Permalänk
Medlem
Plats
Bästkusten
Registrerad
Jun 2009
Skrivet av vallentiin:

Okej, skall skriva ett program som behöver multiplicera tal med varandra i en forloop.
Tex om användaren matar in ett värde av 5 skall programmet skriva ut 5 * 4 * 3 * 2 * 1 = .....( sry orkade inte räkna ut )

for (int i = x; i > 0; i--){
}

hade tänkt att använda mig av denna som bas och fortsätta från där men oavsätt vad jag skriver in så gångrar den fel tal.

tacksam för all hjälp jag kan få.

Och vad är det som inte fungerar?

Klistra in all din kod i CODE-taggar så kan vi se vart felet ligger.

|| Intel 8700K || MSI GTX 1080 TI Gaming X || Xonar DG || Samsung 750 EVO 500GB & OCZ Agility 3 120GB & Samsung 960 EVO 250GB & Crucial V4 256GB || XFX XXX 650W || Antec P183 || Asus G-Sync RoG Swift PG279Q || Dell XPS 15 || Thinkpad X220

The Force is like Duct Tape, it has a light side, a dark side, and holds the universe together.

Trädvy Permalänk
Medlem
Registrerad
Okt 2012

int x; cin >> x; int total = x; for (int i = x ; i > 0; i--) { total = total * i; cout << total << endl; }

om jag skriver in en 4a får jag ( 4 16 48 96 96 )
det skall bli ( 4 12 24 24 )

dator: Intel Core i5 3570K | Noctua NH-D14 | MSI Z77A-GD65 ATX | Corsair 16GB 1600MHz VENGEANCE LP | XFX Core Edition 850W 80+ Bronze | Corsair Carbide 500R | Sapphire Radeon HD 7970 GHz 3GB | Samsung SSD 840 Series 250GB | 2st. 2TB Seagate Barracuda 7200rpm SATA 6Gbit/s | DVD±RW Samsung 24X DL
Kringutrustning: ASUS MX279H 27" | Microsoft sidewinder x4 | Func MS-3 v2

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Okt 2006

I din "initiering" gör du

int total = x;

Varför?

Trädvy Permalänk
Medlem
Plats
Avesta
Registrerad
Sep 2003
Skrivet av vallentiin:

int x; cin >> x; int total = x; for (int i = x ; i > 0; i--) { total = total * i; cout << total << endl; }

om jag skriver in en 4a får jag ( 4 16 48 96 96 )
det skall bli ( 4 12 24 24 )

Skrev en snabb funktion i PHP.

<form method="post"> <input type="number" name="num"> <input type="submit" value="Räkna"> </form> <?php if (isset($_POST['num'])) { multiply($_POST['num']); } function multiply($num) { $total = $num; for($i = $num; $i > 0; $i--) { echo $total . ' * ' . $i . ' = ' . $total * $i . '<br/>'; } } ?>

Resultat:

5 * 5 = 25 5 * 4 = 20 5 * 3 = 15 5 * 2 = 10 5 * 1 = 5

Eller var det inte så du menade?

Stationär i3 8100 + Dark Rock 4 Pro - ROG Strix Z370-E Gaming - 16GB DDR4 3200MHz - MSI RX Vega 56 /w Vega 64 bios + Morpheus II - 960 EVO 500GB - Phanteks Eclipse P400S TG - RM750x - AOC Agon AG271QX
Laptop i7 3630QM - 16GB DDR3 - AMD 7970M - Samsung 850 EVO 250GB

Trädvy Permalänk
Medlem
Registrerad
Okt 2012
Skrivet av Shimonu:

I din "initiering" gör du

int total = x;

Varför?

För att annars deklareras den inte och jag får complie error.

dator: Intel Core i5 3570K | Noctua NH-D14 | MSI Z77A-GD65 ATX | Corsair 16GB 1600MHz VENGEANCE LP | XFX Core Edition 850W 80+ Bronze | Corsair Carbide 500R | Sapphire Radeon HD 7970 GHz 3GB | Samsung SSD 840 Series 250GB | 2st. 2TB Seagate Barracuda 7200rpm SATA 6Gbit/s | DVD±RW Samsung 24X DL
Kringutrustning: ASUS MX279H 27" | Microsoft sidewinder x4 | Func MS-3 v2

Trädvy Permalänk
Medlem
Registrerad
Okt 2012
Skrivet av chif:

Skrev en snabb funktion i PHP.

<form method="post"> <input type="number" name="num"> <input type="submit" value="Räkna"> </form> <?php if (isset($_POST['num'])) { multiply($_POST['num']); } function multiply($num) { $total = $num; for($i = $num; $i > 0; $i--) { echo $total . ' * ' . $i . ' = ' . $total * $i . '<br/>'; } } ?>

Resultat:

5 * 5 = 25 5 * 4 = 20 5 * 3 = 15 5 * 2 = 10 5 * 1 = 5

Eller var det inte så du menade?

Näh tyvärr, de skall gångras med varandra,

5*4*3*2*1 = 120

dator: Intel Core i5 3570K | Noctua NH-D14 | MSI Z77A-GD65 ATX | Corsair 16GB 1600MHz VENGEANCE LP | XFX Core Edition 850W 80+ Bronze | Corsair Carbide 500R | Sapphire Radeon HD 7970 GHz 3GB | Samsung SSD 840 Series 250GB | 2st. 2TB Seagate Barracuda 7200rpm SATA 6Gbit/s | DVD±RW Samsung 24X DL
Kringutrustning: ASUS MX279H 27" | Microsoft sidewinder x4 | Func MS-3 v2

Trädvy Permalänk
Medlem
Plats
Bästkusten
Registrerad
Jun 2009
Skrivet av vallentiin:

För att annars deklareras den inte och jag får complie error.

Initiera den till noll, det är mer logiskt. Om du går igenom din loop med penna och papper så kommer du se varför resultatet blir som det blir, och du hittar enkelt felet.

|| Intel 8700K || MSI GTX 1080 TI Gaming X || Xonar DG || Samsung 750 EVO 500GB & OCZ Agility 3 120GB & Samsung 960 EVO 250GB & Crucial V4 256GB || XFX XXX 650W || Antec P183 || Asus G-Sync RoG Swift PG279Q || Dell XPS 15 || Thinkpad X220

The Force is like Duct Tape, it has a light side, a dark side, and holds the universe together.

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
Skrivet av DunderKlumpen:

Initiera den till noll, det är mer logiskt.

Vore det inte lite mer logiskt att initiera den till 1, med tanke på hur multiplikation fungerar

Trädvy Permalänk
Medlem
Plats
Zion
Registrerad
Apr 2004
Skrivet av vallentiin:

int x; cin >> x; int total = x; for (int i = x ; i > 0; i--) { total = total * i; cout << total << endl; }

om jag skriver in en 4a får jag ( 4 16 48 96 96 )
det skall bli ( 4 12 24 24 )

Det är för att

loop 1:
Total(16) = total(4) * i(4)

loop 2:
Total(48) = total(16) * i(3)
osv

Skriv ut X
sedan en loop med
(int i = x-1; i <1 ; i--)

då får du
Total (4)

första loopen
Total (12) = Total (4) * i (3)

andra loopen
Total (24) = Total (12) * i (2)

tredje loopen
Total (24) = Total (24) * i (1)

[ i5-6600K @ 4.7Ghz || Corsair H110 GTX || 16GB DDR4 || ASUS Z170 Pro Gaming || Asus ROG 1080 Strix @ 2100+/11Ghz+ ]
Unigine Superposition 1080p; 17487 @ Medium; 4594 @ Extreme
"One is always considered mad, when one discovers something that others cannot grasp."
- Ed Wood

Trädvy Permalänk
Medlem
Registrerad
Okt 2012
Skrivet av Ferrat:

Skriv ut X
sedan en loop med
(int i = x-1; i <1 ; i--)

int x; cin >> x; int total = x; for (int i = x -1 ; i > 0; i--) { total = total * i; cout << total << endl; }

thx, nu såg jag felet själv.
Nu funkar allt som det skall, det var det där dumma minustecknet som saknades.

dator: Intel Core i5 3570K | Noctua NH-D14 | MSI Z77A-GD65 ATX | Corsair 16GB 1600MHz VENGEANCE LP | XFX Core Edition 850W 80+ Bronze | Corsair Carbide 500R | Sapphire Radeon HD 7970 GHz 3GB | Samsung SSD 840 Series 250GB | 2st. 2TB Seagate Barracuda 7200rpm SATA 6Gbit/s | DVD±RW Samsung 24X DL
Kringutrustning: ASUS MX279H 27" | Microsoft sidewinder x4 | Func MS-3 v2

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Apr 2013

Det vi letar efter är 5! där '!' utläses fakultet. Vi säger alltså att 5! = 5 * 4 * 3 * 2 * 1. Från definition kan detta skrivas som 5! = 5 * (5 - 1) * (5 - 2) * (5 - 3) * (5 - 4). Så i din for loop vill vi alltså ha

sum = 1;
for (i = 1; 1 < 5; i++)
{
sum = sum + sum * (5 - i);
}

eller alternativt, sum += sum *(5 - i).

Update:

Såg att du redan hade löst det.

Trädvy Permalänk
Medlem
Plats
Lund
Registrerad
Okt 2011
Skrivet av penk:

Det vi letar efter är 5! där '!' utläses fakultet. Vi säger alltså att 5! = 5 * 4 * 3 * 2 * 1. Från definition kan detta skrivas som 5! = 5 * (5 - 1) * (5 - 2) * (5 - 3) * (5 - 4). Så i din for loop vill vi alltså ha

sum = 1;
for (i = 1; 1 < 5; i++)
{
sum = sum + sum * (5 - i);
}

eller alternativt, sum += sum *(5 - i).

Update:

Såg att du redan hade löst det.

Eller ännu enklare sum = sum * i eller sum *= i
Varför göra det mer komplicerat än det är? 1*2*3*4*5 är samma sak som 5*4*3*2*1

Corsair Vengeance LPX 2x8GB DDR4 2666MHz CL16 | Intel Core i7 6700 3,4 GHz 8MB | MSI Z170A KRAIT GAMING | Corsair Force Series 3 120 GB | Seagate SSHD Desktop 2 TB 7200 RPM 3,5" | Creative Sound Blaster Z PCIe | Western Digital 500 GB | Samsung Writemaster | Corsair TX750 V2 750 W | EVGA GeForce GTX 970 4GB SSC ACX 2.0+| Fractal Design Define R5 (Svart)

Trädvy Permalänk
Medlem
Plats
Bästkusten
Registrerad
Jun 2009
Skrivet av perost:

Vore det inte lite mer logiskt att initiera den till 1, med tanke på hur multiplikation fungerar

Precis, jag skulle bara se så ni var vakna

|| Intel 8700K || MSI GTX 1080 TI Gaming X || Xonar DG || Samsung 750 EVO 500GB & OCZ Agility 3 120GB & Samsung 960 EVO 250GB & Crucial V4 256GB || XFX XXX 650W || Antec P183 || Asus G-Sync RoG Swift PG279Q || Dell XPS 15 || Thinkpad X220

The Force is like Duct Tape, it has a light side, a dark side, and holds the universe together.

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Apr 2013

@gaminggirl:
Jag tycker att det är enklare att utgå från att visa satser från definitioner än att sitta och återskapa ett hjul. Men det är väl klart om man har en matematisk bakgrund och inte programmerar så mycket mer än skapa matematiska modeller i Matlab så är det från mitt perspektiv mycket enklare att lösa det på detta sättet. Vet inte riktigt om det går att förklara tydligare än med något exempel kanske om det är intressant.
Tag exempelvis ett heltal n och k, vi definierar ett udda tal som n = 2 * k + 1. Utifrån detta, hur kan vi då visa att summan av två olika udda tal är ett jämt tal?

Bevis:
Antag a och b är udda. Då gäller från definition, för två heltal i och j, att
a = 2 * i + 1
b = 2 * j + 1

a + b = 2 * i + 1 + 2 * j + 1 = 2 * ( i + j + 1), dvs. att a + b är delbart med två. Därför är summan av två udda heltal alltid ett jämt tal.

Jag tycker det är mycket enklare att utgå från vad som egentligen finns tidigare men sen är det väl klart att det kan vara mycket roligare att göra något på egen hand kanske.

Trädvy Permalänk
Entusiast
Testpilot
Plats
Chalmers
Registrerad
Aug 2011

Jag förvånas lite över hur alla exempel i tråden är imperativa och att rekursion inte ens nämnts. Det är förvisso fullt rimligt om syftet är att lära sig for-loopar, men jag är inte förtjust i det sättet att beräkna fakultet. Så here goes!

Just fakultet brukar vara det första exemplet man stöter på när man ska lära sig rekursion, som i korthet innebär att en funktion kallar på sig själv.

Betrakta 5! = 5 · 4 · 3 · 2 · 1 och notera att det också är lika med 5 · 4!, eftersom 4 · 3 · 2 · 1 = 4!.

Mer allmänt gäller för varje positivt heltal n att

n! = n · (n − 1)!

Detta gäller som sagt för positiva heltal. Vi inser kanske att om vi försöker göra likadant för n = 0 skulle vi få att 0! = 0 · (−1)!, och det makes no sense. Vi måste ha ett basfall – den enklaste tänkbara fakulteten, som vi själva definierar – nämligen

0! = 1

Nu kan vi skriva en rekursiv funktion för detta. Det den ska göra är att returnera 1 om och endast om vi försöker beräkna 0!, annars ska den returnera n · (n − 1)!.

I Java kan vår funktion se ut så:

public static int factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } }

Vill vi göra den lite snyggare (men lite svårare att läsa om man inte är van) använder vi ett ternary expression:

public static int factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); }

Om vi inte vill fastna i en oändlig loop om någon kallar på factorial med ett negativt tal som argument kan vi hantera det också:

public static int factorial(int n) { if (n < 0) { throw new IllegalArgumentException("Cannot compute factorial of "+n+" because it is negative."); } return n == 0 ? 1 : n * factorial(n - 1); }

EDIT: Returnerar nu n · (n − 1)! istället för bara (n − 1)!.

5930K • Corsair DP 32 GiB • EVGA GTX 980 • 2x Swift PG278Q
Better SweClockersDisplayPort över USB-C

Köp processor för framtiden™, men inte grafikkort.

Trädvy Permalänk
Medlem
Plats
Lund
Registrerad
Okt 2011
Skrivet av penk:

@gaminggirl:
Jag tycker att det är enklare att utgå från att visa satser från definitioner än att sitta och återskapa ett hjul. Men det är väl klart om man har en matematisk bakgrund och inte programmerar så mycket mer än skapa matematiska modeller i Matlab så är det från mitt perspektiv mycket enklare att lösa det på detta sättet. Vet inte riktigt om det går att förklara tydligare än med något exempel kanske om det är intressant.
Tag exempelvis ett heltal n och k, vi definierar ett udda tal som n = 2 * k + 1. Utifrån detta, hur kan vi då visa att summan av två olika udda tal är ett jämt tal?

Bevis:
Antag a och b är udda. Då gäller från definition, för två heltal i och j, att
a = 2 * i + 1
b = 2 * j + 1

a + b = 2 * i + 1 + 2 * j + 1 = 2 * ( i + j + 1), dvs. att a + b är delbart med två. Därför är summan av två udda heltal alltid ett jämt tal.

Jag tycker det är mycket enklare att utgå från vad som egentligen finns tidigare men sen är det väl klart att det kan vara mycket roligare att göra något på egen hand kanske.

Återskapa ett hjul? Vad har jag återskapat egentligen? Jag har använt grundläggande matematiska lagar kombinerat med definitionen av fakultet för att slippa ha 3 gånger så många operationer per varv i loopen mot vad som är nödvändigt. Förbättrar även läsbarheten. Men visst programmerare är mer av det jag är än matematiker, även om det ingår en hel del matte i min utbildning. Har använt matlab och maple också, skulle inte ha gjort på det viset i någon av dem heller.

Corsair Vengeance LPX 2x8GB DDR4 2666MHz CL16 | Intel Core i7 6700 3,4 GHz 8MB | MSI Z170A KRAIT GAMING | Corsair Force Series 3 120 GB | Seagate SSHD Desktop 2 TB 7200 RPM 3,5" | Creative Sound Blaster Z PCIe | Western Digital 500 GB | Samsung Writemaster | Corsair TX750 V2 750 W | EVGA GeForce GTX 970 4GB SSC ACX 2.0+| Fractal Design Define R5 (Svart)

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Apr 2013

@gaminggirl:
Förlåt om jag är otydlig. Jag menade inte att det var du som hade "återskapat hjulet". Var nog inte ens rätt ordval egentligen. Jag nosade bara kort på vissa exempel tidigare och tyckte bara att det såg lite krångligt ut men sen är jag inte lika van att läsa koden på samma sätt kanske. Men jag förstår hur andra tänker och det sista jag vill är att gå emot någon annans logik - för min del tyckte jag att läsbarheten var trevligare från mitt perspektiv om man skrev koden från mitt sätt. Dessutom om man kan optimera koden så är det ju ännu bättre.
Jag älskar förövrigt den rekursiva lösningen i Java som @Alling gjorde.

Trädvy Permalänk
Medlem
Plats
127.0.0.1
Registrerad
Sep 2003
Skrivet av Alling:

Jag förvånas lite över hur alla exempel i tråden är imperativa och att rekursion inte ens nämnts. Det är förvisso fullt rimligt om syftet är att lära sig for-loopar, men jag är inte förtjust i det sättet att beräkna fakultet. Så here goes!

Jag är nog lite anti mot rekursiva funktioner då det ofta resulterar i stack overflow om man använder sig av det i programmering, dock beror det ju på hur stor data man jobbar på och djupet på rekursionen, så i detta fall skulle det fungera hyfsat.

1: Intel i7-3930K | 32GB Corsair Dominator GT | Asus Rampage IV Extreme x79 | 2 x 1080 GameRock Premium 8GB | 2 x Samsung Pro 840 512GB | Corsair AX1200i | BenQ XL2411 24" / W1070 135" | Bose QC25 | Windows 10 Pro x64 | HTC Vive |
2: Intel Core i7-4700HQ | 32GB RAM | Intel HM87 Express | GTX 780M | 17" | Windows 10 x64 |

Trädvy Permalänk
Entusiast
Testpilot
Plats
Chalmers
Registrerad
Aug 2011
Skrivet av Dalton Sleeper:

Jag är nog lite anti mot rekursiva funktioner då det ofta resulterar i stack overflow om man använder sig av det i programmering, dock beror det ju på hur stor data man jobbar på och djupet på rekursionen, så i detta fall skulle det fungera hyfsat.

Yes, Java är kanske inte det mest optimala språket att skriva rekursiva funktioner i.

5930K • Corsair DP 32 GiB • EVGA GTX 980 • 2x Swift PG278Q
Better SweClockersDisplayPort över USB-C

Köp processor för framtiden™, men inte grafikkort.

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Jun 2002
Skrivet av Alling:

Jag förvånas lite över hur alla exempel i tråden är imperativa och att rekursion inte ens nämnts. Det är förvisso fullt rimligt om syftet är att lära sig for-loopar, men jag är inte förtjust i det sättet att beräkna fakultet. Så here goes!

Just fakultet brukar vara det första exemplet man stöter på när man ska lära sig rekursion, som i korthet innebär att en funktion kallar på sig själv.

Betrakta 5! = 5 · 4 · 3 · 2 · 1 och notera att det också är lika med 5 · 4!, eftersom 4 · 3 · 2 · 1 = 4!.

Mer allmänt gäller för varje positivt heltal n att

n! = n · (n − 1)!

Detta gäller som sagt för positiva heltal. Vi inser kanske att om vi försöker göra likadant för n = 0 skulle vi få att 0! = 0 · (−1)!, och det makes no sense. Vi måste ha ett basfall – den enklaste tänkbara fakulteten, som vi själva definierar – nämligen

0! = 1

Nu kan vi skriva en rekursiv funktion för detta. Det den ska göra är att returnera 1 om och endast om vi försöker beräkna 0!, annars ska den returnera n · (n − 1)!.

I Java kan vår funktion se ut så:

public static int factorial(int n) { if (n == 0) { return 1; } else { return factorial(n - 1); } }

Vill vi göra den lite snyggare (men lite svårare att läsa om man inte är van) använder vi ett ternary expression:

public static int factorial(int n) { return n == 0 ? 1 : factorial(n - 1); }

Om vi inte vill fastna i en oändlig loop om någon kallar på factorial med ett negativt tal som argument kan vi hantera det också:

public static int factorial(int n) { if (n < 0) { throw new IllegalArgumentException("Cannot compute factorial of "+n+" because it is negative."); } return n == 0 ? 1 : factorial(n - 1); }

Du har ju i texten skrivit att man ska returnera n * (n-1)!, men så tycker jag inte att det ser ut i din kod?

Såhär borde det väl vara?

public static int factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } }

Trädvy Permalänk
Entusiast
Testpilot
Plats
Chalmers
Registrerad
Aug 2011
Skrivet av MickeBoy:

Du har ju i texten skrivit att man ska returnera n * (n-1)!, men så tycker jag inte att det ser ut i din kod?

Såhär borde det väl vara?

public static int factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } }

måste du va så dryg attityd? man fattar va man menar,,, va e meningen me o klaga på små detaljer,,,,

Skämt åsido. Obegripligt hur jag kunde klanta till det så. TACK för att du uppmärksammade det! Ska genast ändra.

5930K • Corsair DP 32 GiB • EVGA GTX 980 • 2x Swift PG278Q
Better SweClockersDisplayPort över USB-C

Köp processor för framtiden™, men inte grafikkort.

Trädvy Permalänk
Medlem
Plats
Vancouver, BC
Registrerad
Jul 2009

I Python kanske:

sum = 1 for i in range(2,n+1): sum=*i

Där n är valfritt tal.

H440 | Asus Z170-A | i5 6600K | EK XLC Predator 240 | 16GB 3000 | GTX 1080 | SSD 1.2TB | G2 750W | PG279Q | Vive

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011
Skrivet av Dalton Sleeper:

Jag är nog lite anti mot rekursiva funktioner då det ofta resulterar i stack overflow om man använder sig av det i programmering, dock beror det ju på hur stor data man jobbar på och djupet på rekursionen, så i detta fall skulle det fungera hyfsat.

Håller med. I vissa fall blir det väldigt mycket enklare att lösa ett problem med en rekursiv lösning, men man ska nog akta sig för att använda det som förstatanke. Framförallt när man jobbar i språk som C++, Java och C# då ingen av dessa garanterar att svansrekursion optimeras till en iterativ loop som inte äter stack.

I detta specifika fall är ju en iterativ lösning bland det enklast man kan göra och det är absolut den mest effektiva.

unsigned fac(unsigned n) { if (n <= 1) { return 1; } return n * fac(n - 1); }

är inte svansrekursiv, så går aldrig att optimera.

Går att skriva om så här för att göra den svansrekursiv

unsigned fac(unsigned n, unsigned acc = 1) { if (n <= 1) { return acc; } return fac(n - 1, acc * n); }

men är detta verkligen att föredra över en enkel "for"-loop?

Är heller ingen garanti att detta blir omskriven till en iterativ algoritm av kompilatorn, även om det i praktiken är fallet med de flesta moderna kompilatorer.

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Registrerad
Feb 2016

@Yoshman:

Det kallas recursion det du försöker åstadkomma och antagligen är syftet med uppgiften.
Googla och förstå vad recursion är så kommer du lösa uppgiften lätt.

mvh Filip

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Sep 2008

Att alla ska göra så krångliga lösningar. Här är den ända som behövs:

public static int fac(int n) { int sum = 1; for(int i = n; i > 0; sum*= i--); return sum; }

Skämt åsido, även fast denna fungerar kan man börja argumentera för förståelsen

Däremot vill jag nog tillägga något i rekursion vs iteration debatten. Båda har sina syften och har sina nackdelar och fördelar. Rekursion är extremt bra tillämpat vid algoritmer (divide conquer, merge sort (som java förövrigt utnyttjar i sin collections), men även traversering m.fl). Iteration löses även med hjälp av rekursion i flera funktionella paradigmer, så det är inte fy och skam att lära sig rekursion. Däremot skulle jag argumentera att rekursion är svårare att läsa än iteration där man kan följa flödet och dess vägar.

Summa kardemumma, lär dig båda så kommer du finna nöja med båda i olika situationer.

Edit. Märkte att jag gjorde exemplet i Java, men bör nog vara en 1:1~ konvertering där.

Trädvy Permalänk
Legendarisk
Hedersmedlem
Plats
::1
Registrerad
Dec 2002

Här är en variant som använder constexpr för att om möjligt utföra beräkningen redan vid kompileringstid:

constexpr int factorial(const int n) { return n <= 1 ? n : n * factorial(n - 1); }

Körbart demo:
https://godbolt.org/g/NizxP1

Abstractions all the way down.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

@Tunnelsork: ett lysande exempel på där C++11 är ett klart fall framåt jämfört med tidigare. Samma effekt kan uppnås med pre-C++11 så här

// Rekursiva fallet template<int N> struct factorial { enum { value = N * factorial<N - 1>::value }; }; // Basfallet där N==0 template<> struct factorial<0> { enum { value = 1 }; }; int main() { std::cout << factorial<5>::value << std::endl; }

Kanske lite svårare att följa

För den som absolut inte vill använda "for" i C++ finns faktiskt en del färdiga verktyg i standardbiblioteket. Detta kräver C++11

unsigned factorial(unsigned n) { std::vector<unsigned> seq(n); std::iota(std::begin(seq), std::end(seq), 1); return std::accumulate(std::begin(seq), std::end(seq), 1, std::multiplies<unsigned>()); }

Svårt att se att någon skulle välja detta över en for-loop i just detta fall dock...

Det finns språk som faktiskt saknar for-loopar, ett exempel är Ruby och där skulle nog de flesta köra just varianten ovan här. Fast syntaxen för detta är lite mer lättläst i Ruby.

def factorial(n) n.downto(1).inject(1, &:*) end

Detta säger: starta från n, skapa en sekvens av heltal ner till ett (inklusive). Ta denna sekvens, applicera sedan metoden "*" (multiplicera) på hela sekvensen, left-hand-side är resultatet av föregående beräkning och man startar med 1 (första argumentet till inject).

Samma sak gäller rekursion. Man ska vara försiktig med detta i språk som t.ex. C++, Java och C# då dessa har en fixerad storlek på anropsstacken och de garanterar inte att en konstant mängd stack-utrymme används för svansrekursiva funktioner.

Finns språk där optimering av svansrekursion är en del av språkdefinitionen och typisk saknas där motsvarande "for-loop". Många Lisp-dialekter och i princip alla funktionella språk fungerar så.

Finns också språk/miljöer där anropsstacken kan växa dynamisk, två sådana exempel är Erlang och Go. I det läget väljer man naturligtvis en rekursiv lösning så fort det passar.

I fall där en rekursiv lösning inte kan göras svansrekursiv men ändå är det enklaste sättet och man sitter med C++, Java eller C# så går det alltid att helt mekaniskt att översätta en rekursiv funktion till en iterativ funktion + separat stack. Kanske inte verkar som en förbättring, men det är det då stacken i detta fall ligger på heap:en så den kan växa dynamiskt!

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
Skrivet av Yoshman:

För den som absolut inte vill använda "for" i C++ finns faktiskt en del färdiga verktyg i standardbiblioteket.

Annars kan man ju alltid använda boost

Skrivet av Yoshman:

Det finns språk som faktiskt saknar for-loopar, ett exempel är Ruby och där skulle nog de flesta köra just varianten ovan här.

Ruby har ju dock for-loopar:

res = 1; for i in 1..5 res *= i; end puts "result = #{res}"