Tävlingsprogrammering/Uppgifter/Sifferlek
Sifferlek
Termen digital root för heltalet N innebär att man upprepade gånger summerar talets ingående siffror tills summan blir < 10. Till exempel för talet 34783 får man
3 + 4 + 7 + 8 + 3 = 25
2 + 5 = 7
Talet 34783 har digital root 7.
På liknande sätt definieras multiplicative digital root för heltalet N, där man istället upprepade gånger multiplicerar ingående siffror tills produkten blir < 10. Till exempel för talet 34783 får man
3 · 4 · 7 · 8 · 3 = 2016
2 · 0 · 1 · 6 = 0
Talet 34783 har multiplicative digital root 0. Hos talet 34783 är alltså multiplicative digital root och digital root olika.
Skriv ett program som tar reda på hur många tal i ett givet intervall som har samma digital root som multiplicative digital root. Intervallet ryms alltid mellan 1 och en miljon.
Körningsexempel 1:
Från talet ? 1000 Till talet ? 2000 Antal samma: 33
(Bland dessa finns till exempel 1124, 1355, 1473 och 1977.)
Körningsexempel 2:
Från talet ? 364 Till talet ? 371 Antal samma: 2
Lösning
[redigera]Eftersom intervallet som störst kan vara 1-1000000, så kan man helt enkelt bara gå igenom alla tal och räkna antalet som har samma digital root som multiplicative digital root. Den enda svårigheten kan vara att luska fram siffrorna i ett tal var för sig, men det kan man enkelt göra genom att gå igenom talet från höger till vänster, vilket uträttas med restdivision med 10 (vi får siffran längst till höger i talet) samt heltalsdivision med 10 (siffran längst till höger försvinner, alla siffror förskjuts ett steg åt höger). Man kan förvisso också konvertera talet till en sträng och gå igenom strängen tecken för tecken, men det är inte lika effektivt.
Här nedan följer en naiv implementation i Java, men det finns en smartare (som kommer här efter)...
import java.util.*;
public class Sifferlek
{
//Räknar ut ett tals digital root.
public static int dRoot(int tal)
{
int sum = 0;
while(tal>0) //Så länge det finns siffror kvar i talet...
{
sum += tal%10; //Adderar den sista siffran till summan.
tal /= 10; //Plockar bort den sista siffran (den längst till höger).
}
if(sum<10) return sum;
else return dRoot(sum);
}
//Räknar ut ett tals multiplicative digital root.
public static int mdRoot(int tal)
{
int sum = 1; //Bra att börja med 1 om det rör sig om multiplikation.
while(tal>0) //Så länge det finns siffror kvar i talet...
{
sum *= tal%10; //Multiplicerar den sista siffran till produkten.
tal /= 10; //Plockar bort den sista siffran (den längst till höger).
}
if(sum<10) return sum;
else return mdRoot(sum);
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Från talet ? ");
int from = scan.nextInt();
System.out.print("Till talet ? ");
int to = scan.nextInt();
//Antal samma.
int svar = 0;
//Går igenom alla tal i intervallet.
for(int i = from; i<=to; i++)
{
//Har de samma digital root som multiplicative digital root?
if(dRoot(i)==mdRoot(i)) svar++;
}
//Skriver ut svaret.
System.out.println("\nAntal samma: " + svar);
}
}
Om vi tänker oss att vi redan gått igenom alla tal < N och sparat deras siffersummor respektive sifferprodukter, kan vi snabbt beräkna talet Ns siffersumma respektive sifferprodukt. För siffersumman tar vi helt enkelt bort sista siffran n i talet N, nu har vi ett tal M, siffersumman för talet M har vi redan beräknat och sparat, således blir siffersumman för N = siffersumma(M) + n. Analogt för produkten.
Att ett tals siffersumma respektive sifferprodukt är mindre än talet självt kan vi utnyttja för att få följande lilla snabba program.
import java.util.*;
public class SifferlekV2
{
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Från talet ? ");
int from = scan.nextInt();
System.out.print("Till talet ? ");
int to = scan.nextInt();
//Antal samma.
int svar = 0;
//Digital root för alla tal 0-to.
int [] droot = new int [to+1];
//Multiplicative digital root för alla tal 0-to.
int [] mroot = new int [to+1];
//Sätter alla root för talen <10 till sigsjälva för respektive root.
//Math.min() finns med för specialfallet att to<10.
for(int i = 0; i<Math.min(10,to+1); i++) droot[i] = mroot[i] = i;
//Vi börjar med att beräkna alla tals siffersummor.
for(int i = 10; i<=to; i++)
{
//Ett tals siffersumma är siffersumman för talet man får om man tar bort sista siffran,
//samt adderar sista siffran till summan. T.ex. är droot(56372) = droot(5637)+2.
droot[i] = droot[i/10]+(i%10);
}
//Vi beräknar alla tals sifferprodukter.
for(int i = 10; i<=to; i++)
{
//Ett tals sifferprodukt är sifferprodukten för talet man får om man tar bort sista siffran,
//samt multiplicerar sista siffran till produkten. T.ex. är mroot(8672) = mroot(867)*2.
mroot[i] = mroot[i/10]*(i%10);
}
//Nu ser vi till att alla tal får sin root < 10.
//Alla tal <i har korrekt root. I droot[i] har vi siffersumman lagrad.
//I mroot[i] är sifferprodukten för talet i lagrad. Siffersumman och sifferprodukten för
//ett tal är alltid mindre än talet självt. Detta leder till..
for(int i = 10; i<=to; i++)
{
//...att rooten för talets siffersumma är talets root.
droot[i] = droot[droot[i]];
//...och att multiplikativa rooten för talets sifferprodukt är talets multiplicative root.
mroot[i] = mroot[mroot[i]];
}
//Räknar antalet tal i intervallet som har samma respektive root.
for(int i = from; i<=to; i++) if(droot[i]==mroot[i]) svar++;
//Skriver ut svaret.
System.out.println("\nAntal samma: " + svar);
}
}
Simpel lösning som använder rekurson och moduloräkning:
#include <iostream>
using namespace std;
int digital_root(int tal){
int sum = 0;
while(tal > 0){
sum += tal % 10;
tal /= 10;
}
if (sum >= 10)
return digital_root(sum);
else
return sum;
}
int multiplicative_root(int tal){
int prod = 1;
while(tal > 0){
prod *= tal % 10;
tal /= 10;
}
if (prod >= 10)
return multiplicative_root(prod);
else
return prod;
}
int main(){
int from, to, antal = 0;
cout << "Från talet ? ";
cin >> from;
cout << "Till talet ? ";
cin >> to;
for(int at = from; at <= to; at++){
if (digital_root(at) == multiplicative_root(at))
antal++;
}
cout << "Antal samma: " << antal << endl;
}
För att dela upp ett tal i dess siffror kan man såklart också konvertera talet till en sträng, och sedan se vilka siffror som står på vissa positioner, men det är ungefär ovanstående kod som körs i sådana tal-till-sträng-konverteringar.
Här följer en enkel, svansrekursiv, minnessnål och snabb lösning i C (av Anton Fors Hurdén) som använder vissa insikter, såsom att vi inte behöver fortsätta multiplicera om vår ackumulerade produkt är noll, och att digital root alltid följer ett visst mönster och kan räknas ut i O(1)-tid:
#include <stdio.h>
#define dr(n) (1 + ((n - 1) % 9))
int mdr(int n) {
int p = 1;
while ((p *= n % 10) && (n /= 10));
return p < 10 ? p : mdr(p);
}
int main() {
int f, t, n = 0;
scanf("%d%d", &f, &t);
while (f <= t) n += dr(f) == mdr(f++);
printf("%d\n", n);
}