406 подписчиков

#22. Угадываем число в диапазоне - мощный алгоритм

25 января 202325 янв 2023

160

5 мин

Оглавление

КОД
Примечания по коду

Это статья об основах программирования. На канале я рассказываю об опыте перехода в IT с нуля, структурирую информацию и делюсь мнением.

Хой, джедаи и амазонки!

В одном из уроков Skillbox мы упражнялись в сохранении информации в лог-файл. Задача ставилась так: "Помните, мы делали программу, которая угадывает число в диапазоне до 100? Давайте улучшим её и сделаем вывод в лог-файл, для этого поставьте видео на паузу и..."

Мы делали подобную программу. Но не до 100, а от нуля до десяти - через условия. Циклов тогда ещё не освоили.

Суть программы - она предлагает вариант вашего загаданного числа, а вы говорите "больше", "меньше" или "угадано". И нужно, чтобы программа угадывала с минимально возможного числа попыток.

Вот поставил я видео на паузу и уже несколько вечеров пытаюсь собрать эту программу. Собрал, решил улучшить. В итоге что вышло:

Программа запрашивает максимальное значение из диапазона. Т.е. вы можете загадать 25, но в диапазоне (от нуля) до 100 000 000. А можете загадать 324 и выбрать диапазон до 999 - какой захотите, такой и зададите.
Программа посчитает максимальное число попыток, которое ей потребуется, чтобы отгадать ваше число. Например, для диапазона от 0 до 100 000, программе потребуется 17 попыток.
Программа рассчитывает ваше число через алгоритм, используя ваши подсказки, и сохраняет отчёт в лог-файл.

Далее покажу код, а после - пару слов о нескольких функциях и решениях. Для решения задачи мне понадобилось четыре пакета:

fmt;
math (округление, логарифм);
os (создан лог-файл);
strconv (конвертация числа в строку).

КОД

package main

import (
"fmt"
"math"
"os"
"strconv"
)

func main() {
fmt.Println("Я угадаю твоё число с минимального числа попыток. Отвечай +, - или напиши Да. + означает, что ваше число больше моего, - что ваше число меньше моего. И Да означает, что я угадал ваше число")
fmt.Println("-------------")
fmt.Println("Загадайте число и введите диапазон, в котором мы угадываем: от 0 до...")

var max int
fmt.Scan(&max)
maxTry := math.Ceil(math.Log2(float64(max)))
fmt.Printf("Угадаю ваше число максимум с %v попыток.\n", maxTry)
maxNum := max
minNum := 1
midNum := maxNum / 2

file, err := os.Create("Lof-file.txt")
if err != nil {
fmt.Println("Ну удалось создать файл", err)
return
}
defer file.Close()
var sLog string

file.WriteString(strconv.Itoa(midNum))
file.WriteString("\n")

OutLoop:
for i := 1; ; i++ {
fmt.Println("Попытка №:", i)
fmt.Printf("Ваше число %v? \n", midNum)

var answerHuman string
fmt.Scan(&answerHuman)

switch answerHuman {
case "Да":
fmt.Print("Угадал!")
sLog = "Угадал!"
file.WriteString(sLog)

break OutLoop
case "-":
maxNum = midNum
midNum = (minNum + maxNum) / 2
if maxNum == midNum {
midNum--
}
case "+":

minNum = midNum
midNum = (minNum + maxNum) / 2
if minNum == midNum {
midNum++
}
default:
fmt.Print("Ожидался другой ответ")
sLog = "Ожидался другой ответ"
file.WriteString(sLog)
return
}
file.WriteString(strconv.Itoa(midNum))
file.WriteString("\n")
if midNum > max {
fmt.Println("Ожидалось, что загаданное число не больше верхнего значения диапазона.")
break
}
}
fmt.Println(file.Name())
}

Примечания по коду

Далее я рассказываю о лайфхаках, которые считаю интересными

Определяем максимальное число попыток, чтобы угадать число

Чтобы найти максимальное число попыток, я использвал код:

var max int
fmt.Scan(&max)
maxTry := math.Ceil(math.Log2(float64(max)))
fmt.Printf("Угадаю ваше число максимум с %v попыток.\n", maxTry)

Что здесь интересного? В третьей строке происходит магия. Если не вдаваться в математические детали, то 2 в степени количества максимальных попыток угадывания равняется верхнему пределу диапазона угадывания.

Пример: 2^8=256 (столько же было мегабайт ОЗУ на моём первом ПК). Т.е. в диапазоне от 1 до 256, нужно не больше 8 попыток для угадывания при заданном алгоритме.

Чтобы найти эту восьмёрку, нужно воспользоваться логарифмом по основанию 2:

8 = log2(256).

Т.е. сперва задаём переменную max, считываем её - это максимальное значение диапазона для поиска числа пользователя.

При инициализации переменной max я использовал тип данных int, т.к. он мне нужен дальше. А для расчёта логарифма, нужно переконвертировать переменную типа int во float64. Так появилось выражение

math.Log2(float64(max))

Далее нужно округлить значение, т.к. если этого не сделать, то в выводе в терминал получим примерно следующую картину:

"Нужно 7,395452358345 попыток, чтобы угадать ваше число". Соответственно, нас это не устроит и нужно округлить число. Проблема в том, что привычная функция Round округляет по правилам математики, а нам нужно округление в большую сторону. Для этого используем функцию Ceil пакета math.

math.Ceil(math.Log2(float64(max)))

Вывод текста в лог-файл

Чтобы сохранить цифры в лог-файл, я воспользовался функцией Itoa (integer to ASCII, пришло из языка С/UNIX) пакета strconv.

file.WriteString(strconv.Itoa(midNum))
file.WriteString("\n")

Затем добавил перенос строки. Возможно можно сделать это в одну строчку, просто не нашёл нужного синтаксиса. Пока получилось так.

Остальное

Дальше, на мой взгляд, просто математика. Единственно, интересен форматированный вывод, постепенно осваиваюсь с ним:

fmt.Printf("Ваше число %v? \n", midNum)

Очень полезно бывает освоить хотя бы базовые команды форматированного вывода. А ещё по началу трудно запомнить, как сделать перенос строки - впишите \n (слеш не тот, что рядом с num lock).

Вот так, продолжаю изучать Golang. Немножко зависаю на темах обучения, не рвусь вперёд - хочу получше освоить каждый пакет. На очереди strings: