Beräkna antalet gånger noll dyker upp mellan två heltal: n, m där n≤m
Hej,
som det står i rubriken vill jag alltså beräkna hur många gånger 0 dyker upp mellan talen m, n (inklusive dessa två) där n≤m men vet inte riktigt hur jag ska gå till väga förutom att då skriva upp varenda tal och beräkna.
Det jag tänkt på än så länge (som jag tror stämmer) är att 0 kommer dyka upp maximalt 1 gång för varje siffra mellan 0-9 till vänster om sig självt. Generellt sett så funkar detta förstås inte om vi t.ex. har talet n=1000 och m=1024, eftersom då kommer tiotalet bara bli 0 tre gånger, en gång för 0, 1, 2 etc.
Vet knappt vad jag snackar om! Någon som har några tips?
Tack på förhand!
Kan du skriva av hela uppgiftslydelsen?
"A Benedict monk No. 16 writes down the decimal representations of all natural numbers between and including m and n, m≤n. How many 0’s will he write down?"
Det är en programmeringsuppgift egentligen men måste förstå hur jag ska resonera matematiskt innan jag ens kan börja tänka på hur jag ska skriva en algoritm av detta. Antar att det är något mönster jag behöver urskilja?
Hej! Svaret behöver ingen algoritm; så som uppgiften är formulerad är svaret Oändligheten.
Decimalutvecklingen av det naturliga talet 2 innehåller oändligt många nollor 2.00000000000000000000000000000000000000000000000000000000... .
Albiki
Det naiva sättet att lösa det på är att gå igenom alla tal mellan m och n och räkna hur många nollor det finns i dom.
Man kan däremot göra det effektivare, men det krävs nog lite pillande, jag vill minnas att jag gjort något liknande någon gång. För att ge lite tips på hur man kan tänka.
- Gör en funktion F(n) som kan ge dig antalet nollor man måste skriva om man skriver ned talen från 0 till n. Antalet nollor man måste skriva om man skriver talen mellan m och n är då F(n) - F(m - 1).
- För att kunna göra F(n) effektiv, försök börja med specialfall. Hur många nollor behöver du skriva då n = 9? n = 99, n = 999, n = 99999999?
- Hur många nollor behöver du skriva då n = 1000, 2000, 3000, 4000, 5000?
- Om du nu har n = 1234, vad får du om du beräknar exempelvis något som F(1000) + F(200) + F(30) + F(4)? (Detta blir nog inte helt rätt, men om man går igenom det noggrant så kan man komma fram till sätt att beräkna det på).
Albiki skrev : Hej! Svaret behöver ingen algoritm; så som uppgiften är formulerad är svaret Oändligheten.
Decimalutvecklingen av det naturliga talet 2 innehåller oändligt många nollor 2.00000000000000000000000000000000000000000000000000000000... .
Albiki
Det är väl decimal expansion du menar nu? :P
Stokastisk skrev :Det naiva sättet att lösa det på är att gå igenom alla tal mellan m och n och räkna hur många nollor det finns i dom.
Ja, försökte göra en s.k bruteforce approach först men den blev alldeles för långsam för de större talen.
Att ställa upp det så som du beskrev verkar vettigt, ska försöka göra det. Tack så mycket! Återkommer om jag lyckas eller ej, haha.
Såhär löste jag det:
Först studerade jag en funktion f(N) som räknar antalet nollor i uppräkningen 1..N
Om du har ett tal N som inte innehåller några nollor är det enkelt, man delar bara med 10 per sifferplats för att summera det antal gånger vi snurrat förbi nollan Exempel: N=1234
Vi delar 1234 med 10^1 erhåller 123*10^0=123.
Vi delar 1234 med 10^2 och erhåller 12*10=120
Vi delar 1234 med 10^3 och erhåller 1*10^2=100
Summa: 343 nollor
Saker blir lite mer komplicerade när talet innehåller 0:or eftersom vi då inte har snurrat förbi ett "helt" varv. Vi måste då dra ifrån en korrektionsterm (för varje nolla). Exempel
N=12045
Vi delar med 10 och erhåller 1204*10^0=1204
Vi delar med 10^2 och erhåller 120*10^1=1200
Vi delar med 10^3 och erhåller 12*10^2=1200
Vi delar med 10^4 och erhåller 1*10^3=1000
Delsumma: 4604
Korrektion för nollan på plats 3, -(99-45)=-54. _Varje_ nolla måste korrigeras "fullt ut".
Total Summa: 4550
Antalet nollor mellan två tal n och m ges av f(m)-f(n-1).
Exempel på matlabkod
Tack så jättemycket för ditt svar, hade inte listat ut vad man behövde göra åt 0:orna i talen på egen hand! Nu fick jag äntligen min att fungera.
Markerar tråden som löst.
Ja :)
Det går faktiskt att optimera algoritmen ytterligare, t.ex. att reducera den till bara en loop.
Vill man göra det riktigt "snyggt" kan man göra en rekursiv variant där man anropar med talet N som en sträng (varje anrop skiftar ut en siffra) och returnerar antalet nollor per "plats". Det blir bara några rader kod och fullständigt obegripligt för den som ska rätta :)
