Минимальное количество шагов

@lexatorgas · Регистрация: 25.06.2017

Author24 — интернет-сервис помощи студентам

Всем доброго дня!

Прошу натолкнуть на мысль как решать данную задачу.

На вход дается 2 числа, X и Y. По условию X<=Y.
За 1 шаг я могу либо увеличить X на 2, либо увеличить X в 3 раза.
За какое минимальное кол-во шагов я смогу получить из числа X число Y, если это возможно.

Возможно существует какой-то алгоритм для решения такого типа задач, буду благодарен если натолкнете на него.

@Wolfdp · 20.01.2019, 11:08

начиная с X >= 1 увеличение в 3 раза будет давать больший прирост, нежели +2. До этого числа -- вообще идти в обратную сторону. Дальше либо развлекатся с выводом формулы (мне лень) либо тупо циклом (на больших числах будет работать медленее).

@lexatorgas · 21.01.2019, 09:46 **[ТС]**

UP! Тема актуальна! Идей нет

@Элд Хасп · 21.01.2019, 10:31

Сообщение от lexatorgas

На вход дается 2 числа, X и Y. По условию X<=Y.
За 1 шаг я могу либо увеличить X на 2, либо увеличить X в 3 раза.
За какое минимальное кол-во шагов я смогу получить из числа X число Y, если это возможно.

Если надо получить именно Y? а не число большее или равное Y, то условиям задачи это не всегда возможно.
Самый простой пример. X - чётное число, Y - нечётное (или наоборот). Никакими комбинациями +2 и *3 из X получить Y нельзя.

Уточните условия задачи.

И эта задача всё же относится к математике (арифметике), а не к программированию. Что здесь программировать?

@Рядовой · 21.01.2019, 11:16

Сообщение от lexatorgas

Идей нет

чего тут думать?

C#

 static void Main(string[] args)
        {
            int X = int.Parse(Console.ReadLine());
            int Y = int.Parse(Console.ReadLine());
            int counter = 0;
            for (; ; )
            {
                if (X * 3 <= Y)
                {
                    X *= 3;
                    counter++;
                    continue;
                }
                else if (X + 2 <= Y)
                {
                    X += 2;
                    counter++;
                    continue;
                }
                if (X >= Y || X + 2 > Y) break;
            }
            if (X == Y) Console.WriteLine($"Можно получить за {counter} шагов");
            else Console.WriteLine("Нельзя получить");
            Console.Read();
        }

@Элд Хасп · 21.01.2019, 11:34

Сообщение от Рядовой

чего тут думать?

Решение не всегда даст верный ответ.
А при X=0, вообще, зависнет.

@Рядовой · 21.01.2019, 11:43

Элд Хасп, ну да, 0 и отрицательные не учитывал

Добавлено через 4 минуты
там по хорошему каждый шаг надо чекать расстояние до Y,
но автора надо было натолкнуть на решение

@lexatorgas · 21.01.2019, 11:55 **[ТС]**

Сообщение от Рядовой

чего тут думать

Ну смотри, если на ввод даем 12 и 44 программа выводит 5 шагов, хотя правильно будет 3.

12+2=14
14*3 = 42
42+2 = 44

Добавлено через 2 минуты

Сообщение от Элд Хасп

Уточните условия задачи.

Условия такие: X всегда меньше либо равно Y, 1<=Y<=100.

@Элд Хасп · 21.01.2019, 11:57

Сообщение от Рядовой

ну да, 0 и отрицательные не учитывал

Ну, не только. Возьмите X=2, Y = 12. Ваше решение даст ответ 4, а правильный ответ 2.

Сообщение от Рядовой

но автора надо было натолкнуть на решение

При правильных условия (ТЗ - неполное), решение чисто арифметическое. На уровне 3-4 класса школы.
Что здесь программировать не вижу.

@Рядовой · 21.01.2019, 12:04

Согласен, с ходу решить не удалось

@Элд Хасп · 21.01.2019, 12:10

lexatorgas, если условия задачи звучат так, на каком шаге X станет больше или равно Y, то решение такое:

если оба X и Y < 1, то от X к Y "идём" только через +2. Отсюда количество шагов = модулю (X-Y) делённому на 2 с округлением до ближайшего большего целого.
если X >= 1, то "идём" только через *3. Отсюда количество логарифм по основанию три от Y/X, с округлением результата до ближайшего большего целого.
если X < 1, а Y >=1, то считаем до 1 по первому методу, после по второму. Результат их сумма.

@lexatorgas · 21.01.2019, 12:12 **[ТС]**

Сообщение от Элд Хасп

если условия задачи звучат так,

Уточнил условия: X и Y всегда больше 0

@Элд Хасп · 21.01.2019, 12:19

Сообщение от lexatorgas

Уточнил условия: X и Y всегда больше 0

Решение выше. Оно не меняется, но можно чуть упростить.

если оба X и Y < 1, то от X к Y нужен только 1 шаг.
если X >= 1, то "идём" только через *3. Отсюда количество - логарифм по основанию три от Y/X, с округлением результата до ближайшего большего целого.
если X < 1, а Y >=1, то количество - логарифм по основанию три от Y/(X+2), с округлением результата до ближайшего большего целого и плюс один.

@Элд Хасп Модератор 15456 / 10703 / 2784 Регистрация: 21.04.2018 Сообщений: 31,516 Записей в блоге: 2
	21.01.2019, 12:19	13
	Сообщение от lexatorgas Уточнил условия: X и Y всегда больше 0 Решение выше. Оно не меняется, но можно чуть упростить. если оба X и Y < 1, то от X к Y нужен только 1 шаг. если X >= 1, то "идём" только через *3. Отсюда количество - логарифм по основанию три от Y/X, с округлением результата до ближайшего большего целого. если X < 1, а Y >=1, то количество - логарифм по основанию три от Y/(X+2), с округлением результата до ближайшего большего целого и плюс один. 0

@lexatorgas 0 / 0 / 0 Регистрация: 25.06.2017 Сообщений: 60
		1
	Минимальное количество шагов 20.01.2019, 10:03. Показов 2651. Ответов 12 Метки нет (Все метки) Всем доброго дня! Прошу натолкнуть на мысль как решать данную задачу. На вход дается 2 числа, X и Y. По условию X<=Y. За 1 шаг я могу либо увеличить X на 2, либо увеличить X в 3 раза. За какое минимальное кол-во шагов я смогу получить из числа X число Y, если это возможно. Возможно существует какой-то алгоритм для решения такого типа задач, буду благодарен если натолкнете на него. 0

@Wolfdp 1693 / 1322 / 316 Регистрация: 15.06.2012 Сообщений: 5,034 Записей в блоге: 3
	20.01.2019, 11:08	2
	начиная с X >= 1 увеличение в 3 раза будет давать больший прирост, нежели +2. До этого числа -- вообще идти в обратную сторону. Дальше либо развлекатся с выводом формулы (мне лень) либо тупо циклом (на больших числах будет работать медленее). 0

@lexatorgas 0 / 0 / 0 Регистрация: 25.06.2017 Сообщений: 60
	21.01.2019, 09:46 [ТС]	3
	UP! Тема актуальна! Идей нет 0

@Элд Хасп Модератор 15456 / 10703 / 2784 Регистрация: 21.04.2018 Сообщений: 31,516 Записей в блоге: 2
	21.01.2019, 10:31	4
	Сообщение от lexatorgas На вход дается 2 числа, X и Y. По условию X<=Y. За 1 шаг я могу либо увеличить X на 2, либо увеличить X в 3 раза. За какое минимальное кол-во шагов я смогу получить из числа X число Y, если это возможно. Если надо получить именно Y? а не число большее или равное Y, то условиям задачи это не всегда возможно. Самый простой пример. X - чётное число, Y - нечётное (или наоборот). Никакими комбинациями +2 и *3 из X получить Y нельзя. Уточните условия задачи. И эта задача всё же относится к математике (арифметике), а не к программированию. Что здесь программировать? 0

@Элд Хасп Модератор 15456 / 10703 / 2784 Регистрация: 21.04.2018 Сообщений: 31,516 Записей в блоге: 2
	21.01.2019, 11:34	6
	Сообщение от Рядовой чего тут думать? Решение не всегда даст верный ответ. А при X=0, вообще, зависнет. 0

@Рядовой 1514 / 905 / 328 Регистрация: 17.05.2015 Сообщений: 3,417
	21.01.2019, 11:43	7
	Элд Хасп, ну да, 0 и отрицательные не учитывал Добавлено через 4 минуты там по хорошему каждый шаг надо чекать расстояние до Y, но автора надо было натолкнуть на решение 0

@lexatorgas 0 / 0 / 0 Регистрация: 25.06.2017 Сообщений: 60
	21.01.2019, 11:55 [ТС]	8
	Сообщение от Рядовой чего тут думать Ну смотри, если на ввод даем 12 и 44 программа выводит 5 шагов, хотя правильно будет 3. 12+2=14 143 = 42 42+2 = 44 Добавлено через 2 минуты* Сообщение от Элд Хасп Уточните условия задачи. Условия такие: X всегда меньше либо равно Y, 1<=Y<=100. 0

@Элд Хасп Модератор 15456 / 10703 / 2784 Регистрация: 21.04.2018 Сообщений: 31,516 Записей в блоге: 2
	21.01.2019, 11:57	9
	Сообщение от Рядовой ну да, 0 и отрицательные не учитывал Ну, не только. Возьмите X=2, Y = 12. Ваше решение даст ответ 4, а правильный ответ 2. Сообщение от Рядовой но автора надо было натолкнуть на решение При правильных условия (ТЗ - неполное), решение чисто арифметическое. На уровне 3-4 класса школы. Что здесь программировать не вижу. 0

@Рядовой 1514 / 905 / 328 Регистрация: 17.05.2015 Сообщений: 3,417
	21.01.2019, 12:04	10
	Согласен, с ходу решить не удалось 0

@Элд Хасп Модератор 15456 / 10703 / 2784 Регистрация: 21.04.2018 Сообщений: 31,516 Записей в блоге: 2
	21.01.2019, 12:10	11
	lexatorgas, если условия задачи звучат так, на каком шаге X станет больше или равно Y, то решение такое: если оба X и Y < 1, то от X к Y "идём" только через +2. Отсюда количество шагов = модулю (X-Y) делённому на 2 с округлением до ближайшего большего целого. если X >= 1, то "идём" только через *3. Отсюда количество логарифм по основанию три от Y/X, с округлением результата до ближайшего большего целого. если X < 1, а Y >=1, то считаем до 1 по первому методу, после по второму. Результат их сумма. 0

Опции темы

@lexatorgas 0 / 0 / 0 Регистрация: 25.06.2017 Сообщений: 60
	21.01.2019, 12:12 [ТС]	12
	Сообщение от Элд Хасп если условия задачи звучат так, Уточнил условия: X и Y всегда больше 0 0