Anders Hesselbom

Hur svårt är det att gissa ett tal?

2020-12-28

En person tänker på ett tal mellan 1 och 100, och en annan ska gissa vilket. Om den som gissar skulle gissa fel, så får han reda på om han har gissat på ett för stort eller för litet tal. Den bästa strategin för att gissa rätt på så få försök som möjligt, är att försöka diskvalificera så många tal som möjligt.

Genom att gissa på 10 och få höra att talet är för stort, är genast 91 tal diskvalificerade, och rätt svar måste vara mellan 1 och 9, men man kan lika gärna (och troligen) få höra att talet är för litet, och då är bara 10 tal (1 till 10) diskvalificerade medan 90 tal fortfarande kan vara aktuella.

Smartast är att gissa på 50. Är det fel svar, diskvalificerar det ändå fler än hälften av alla tal mellan 1 och 100, oberoende av om 50 är för stort eller inte. Skulle det vara för stort gissar man på 25, skulle det vara för litet gissar man på 75, och så vidare. Den vinnande strategin för den som gissar på ett tal är alltså att dra av hälften av talrymdens storlek och addera det till eller dra bort det ifrån senaste gissning.

Eftersom det finns en bästa strategi för den som gissar, så kommer antalet försök att hitta ett tal alltid bli detsamma för ett specifikt tal. Personen tänker på talet 50, kommer den som gissar att hitta talet på första försöket. För att mäta hur lång tid det tar att hitta ett specifikt tal, och för att slippa sitta med en vän och gissa på tal hela veckan, har jag skapat två enkla robotar.

Roboten Conny kan tänka på ett tal och be någon att gissa. Roboten Steven kan gissa på tal, och är dessutom bekant med gissningsstrategin jag beskrev ovan. Detta är Conny:

public class NumberThinkingRobot
{
    private readonly ICanGuess _guesser;
    private readonly int _correct;

    public NumberThinkingRobot(int correct, ICanGuess guesser)
    {
        _correct = correct;
        _guesser = guesser;
    }

    public void Begin()
    {
        var tryCount = 0;
        do
        {
            Console.WriteLine($"Try no. {++tryCount}");

            var guess = _guesser.Guess();

            if (guess < _correct)
                _guesser.TooSmall();
            else if (guess > _correct)
                _guesser.TooLarge();
            else
            {
                Console.WriteLine("Correct!");
                break;
            }
        } while (true);
    }
}

Och detta är Steven:

public class NumberGuessingRobot : ICanGuess
{
    private readonly int _max;
    private int _correct;
    private double _stepSize;

    public NumberGuessingRobot(int max)
    {
        _max = max;
        _correct = _max/2;
        _stepSize = _correct;
    }

    public int Guess()
    {
        Console.WriteLine($"Guess: {_correct}");
        return _correct;
    }

    public void TooSmall()
    {
        Console.WriteLine("Too small!");

        _stepSize /= 2.0;
        _stepSize = _stepSize < 1
            ? 1
            : _stepSize;

        _correct += (int)Math.Round(_stepSize);
        _correct = _correct > _max
            ? _max
            : _correct;
    }

    public void TooLarge()
    {
        Console.WriteLine("Too large!");

        _stepSize /= 2.0;
        _stepSize = _stepSize < 1
            ? 1
            : _stepSize;

        _correct -= (int)Math.Round(_stepSize);
        _correct = _correct < 1
            ? 1
            : _correct;
    }
}

Programmet presenteras i sin helhet sist. Så låt oss instruera Conny att det korrekta talet är 22, och instruera Steven att det högsta tillåtna talet är 100, för att sedan fösa ihop dem.

using System;

const int max = 100;
const int correct = 22;
var steven = new NumberGuessingRobot(max);
var conny = new NumberThinkingRobot(correct, steven);
conny.Begin();

Vi kan konstatera att Steven behöver ha fem försök för att hitta 22. Detta är resultatet av körningen:

Try no. 1
Guess: 50
Too large!
Try no. 2
Guess: 25
Too large!
Try no. 3
Guess: 13
Too small!
Try no. 4
Guess: 19
Too small!
Try no. 5
Guess: 22
Correct!

Så hur svåra är de olika talen mellan 1 och 100 att hitta? 50 hittas direkt och 25 och 75 hittas på två gissningar. 13, 37, 63 och 87 kräver tre gissningar. 7 19, 31, 43, 57, 69, 81 och 93 kräver fyra. För 4, 10, 16, 22, 28, 34, 40, 46, 54, 60, 66, 72, 78, 84, 90 och 96 krävs fem gissningar. Resterande sextionio tal kräver sex gissningar eller fler, vilket innebär att det i snitt tar nästan sex gissningar att hitta rätt med den bästa strategin.

Om man istället ska gissa på ett tal mellan 1 och 1000 så har vi tio gånger så många alternativ till korrekt tal, men strategin kräver bara i snitt nio gissningar. Om vi har hundra gånger så många alternativ (ett tal mellan 1 och 10.000) krävs i snitt ungefär 12 gissningar, och för att gissa ett tal mellan 1 och 100.000 krävs knappt 16 gissningar.

Här är programmet i sin helhet (C#9):

using System;

const int max = 100;
const int correct = 22;
var steven = new NumberGuessingRobot(max);
var conny = new NumberThinkingRobot(correct, steven);
conny.Begin();

public class NumberThinkingRobot
{
    private readonly ICanGuess _guesser;
    private readonly int _correct;

    public NumberThinkingRobot(int correct, ICanGuess guesser)
    {
        _correct = correct;
        _guesser = guesser;
    }

    public void Begin()
    {
        var tryCount = 0;
        do
        {
            Console.WriteLine($"Try no. {++tryCount}");

            var guess = _guesser.Guess();

            if (guess < _correct)
                _guesser.TooSmall();
            else if (guess > _correct)
                _guesser.TooLarge();
            else
            {
                Console.WriteLine("Correct!");
                break;
            }
        } while (true);
    }
}

public class NumberGuessingRobot : ICanGuess
{
    private readonly int _max;
    private int _correct;
    private double _stepSize;

    public NumberGuessingRobot(int max)
    {
        _max = max;
        _correct = _max/2;
        _stepSize = _correct;
    }

    public int Guess()
    {
        Console.WriteLine($"Guess: {_correct}");
        return _correct;
    }

    public void TooSmall()
    {
        Console.WriteLine("Too small!");

        _stepSize /= 2.0;
        _stepSize = _stepSize < 1
            ? 1
            : _stepSize;

        _correct += (int)Math.Round(_stepSize);
        _correct = _correct > _max
            ? _max
            : _correct;
    }

    public void TooLarge()
    {
        Console.WriteLine("Too large!");

        _stepSize /= 2.0;
        _stepSize = _stepSize < 1
            ? 1
            : _stepSize;

        _correct -= (int)Math.Round(_stepSize);
        _correct = _correct < 1
            ? 1
            : _correct;
    }
}

public interface ICanGuess
{
    int Guess();
    void TooSmall();
    void TooLarge();
}

Categories: C#, Science