Из заданного числа используя заданный набор операций получить единицу

Задача относится к теме Динамическое программирование но я не могу понять где тут динамика. Хотя решил порядка 10 задач на динамику. Буду благодарен за любой совет или код

1

Сообщение от Новичок Как всегда от противного доказываем?

Конечно! Как это ни противно

1

Сообщение от Байт Есть теорема об однозначном разложении на простые множители.

Намекаете на то что поскольку 2 и 3 простые то никакое произведение двоек неспособно породить труйку в виде сомножителя? Что касается учеников 5-х классов, то учту.

2

Сообщение от IGPIGP Намекаете на то

Намек понят. Это приятно.

1

Сообщение от Байт Намек понят. Это приятно.

Доказательство в виде размышлений красиво, конечно, но не обладает общностью в смысле расширяемости. Хотелось бы уравнений. Ну с чётностью и делимостью степеней 2 на 3 всё более-менее ясно.
2ⁿ=3p
где p должно быть чётно так как 3 - нечётно а слева - чётное число. Причём каков бы нибыл ранг чётности (выделяемая степень 2-ки в качестве сомножителя) числа p, либо слева сократится до 1, либо справа сократится вся чётная часть, а слева останется минимум 2. То есть, невозможно.
Байт, меня интересовал, более сложный вопрос. Я имею соображения, конечно, но я не такой математик чтобы не слушать, а говорить. В разделе физика, например, мне говорить легче.
Но раз математики молчат, придётся мне провоцировать обсуждение своими сентенциями. Скорее всего наивными, с точки зрения математиков. Итак вопрос:
Когда имеет смысл делить на 2 ?
Я пришёл к выводу, что это имеет смысл делать тогда,
когда число делимо на 4, или если результат сокращения на 2 уменьшенный на 1 cократим на 3.
Мои нехитрые мысли я вначале изложил сумбурно и неверно, а в процессе редактирования понял, что не успеваю написать всё как хотелось бы. Может позже.
Байт, я понимаю как это выглядит с точки зрения математиков. Вот почему я хотел слушать, а не говорить.
На одном канадском сайте (QUORA -очень известный сайт) я объяснял почему ускорение направлено именно внутрь кривой траектории. Сочинилась вот такая шутка:

Когда физики говорят о математике, они многозначительно кивают в тон упрощённым и интуитивным суждения, раздувают щёки и даже двигают ушами. Когда инженеры говорят о физике, картина та же. Но когда инженеры говорят о математике, они пляшут с бубном и оглашают окрестности дикими экстатическими воплями. А поскольку я инженер, то я не буду искать новых путей. Итак рассмотрим круговую траекторию как график функции вида ...

и далее по тексту.
То есть как-то так. Надеюсь, это улыбнуло.

2

Сообщение от IGPIGP Когда имеет смысл делить на 2 ?

Может быть вы имели в виду нечто вроде этого.
Пусть есть 2 числа N > M. Тогда есть несколько путей, ведущих из N в M (под "путем" я имею в виду совокупность шагов допустимого вида). И для некоторых пар (N, M) оптимальным является путь, не содержащий делений на 2.
Наверное, не трудно показать, что это действительно так. И даже провести исчерпывающее исследование таких пар. Однако, я не уверен, что это как-то поможет решению задачи. Но само исследование множества таких пар может представлять некоторый, чисто математический интерес. (Ведь каких только задач не придумывают себе Математики! И с каким удовольствием пытаются их решить!)

Добавлено через 20 минут
А что касается моего вполне неуклюжего алгоритма из поста 4, то конечно, все нужно делать ровно наоборот. То есть идти от заданного числа вниз.
Детали ввиду сегодняшней жары изложить не берусь.
Но идея такая. Заводим массив int *x = malloc(N+1). Заполняем его -1, а x[1] = 0
Теперь берем n. Если x[n] неотрицательно, проходим обратно по пути приведшему нас в эту точку и расставляем там x[n]+1, x[n]+2 и т.д. если там уже не стоят меньшие неотрицательные числа.
В противном случае рекурсивно исследуем n-1, n/2, n/3
Не исключено, что нечто похожее уже предлагалось в этой теме, но опять же - жара!
ЗЫ. Имхо, такой подход вполне может претендовать на звание "динамического"

2

Задача интерсная. Но без рекурсии ее тяжко решить. Первое: минимальных путей может быть несколько. Если нужно определить только один путь, неважно какой, то просто.(Если все минимальные пути, то напишите и я дам код)
Второе, максимальный путь - это путь уменьшения на 1.
Поэтому напишем простенькую функцию нахождения минимального пути
Данный алгоритм несовершенен и его существенно можно ускорить, так как он проходит самый длинный путь при уменьшении на 1 при больших числах. это просто так набросок решения в лоб. Если нужно - пишите. но для затравки - просто нужно отсекать более длинные пути. так как решение уже есть по части, соотвественно мы можем удалять те, которые длиннее на каком то отрезке. Более подробно, если будет вопрос/запрос

1

Сообщение от Байт Может быть вы имели в виду нечто вроде этого.

Почти. Я не хотел выглядеть 5-класником с бубном и дикими прыжками.
Думал Вы меня избавите от этой чаши. Хотя мне ли в первой ли? Ой, как говорится, - ЛИ.
Я вчера наночь глядя пытался изложить, но вместо этого наложил так, что еле-еле потом всё убрал. Но видно придётся ещё разик.

Сообщение от Байт И для некоторых пар (N, M) оптимальным является путь, не содержащий делений на 2.

Вообще говоря, строгий анализ можно провести ретроспективно, начиная с конечного результата равного 1. Там видно, что последней операцией могут быть все 3, но две последних равнозначны для 2-ки, то есть нет разницы между 2/2 и 2-1. Кроме всего число 3 так же может быть предпоследним. Далее видно что 4 ведёт к двум равнозначным путям 4-1 3/3 и 4/2 2/2.
И так далее. Это возможно, но громоздко.
Мне нравится матиндукция. Рекурсия везде даёт чудовищный прирост снижения сложности.
И так начали. Но имейте ввиду, дорогой Байт, всё дальнейшее - результат полного отсутствия выбора.

Асеоматика и терминология.
Назовем операцией A преобразование уменьшающее число a0 : например, A(a0) = D3 (деление на 3) или A(a0) = D2 (деление на 2) или A(a0) = D1 (вычитание 1).
Поскольку задача состоит в максимально быстром уменьшении исходного числа, то операции по эффективности можно расположить в следующем порядке: D3 > D2 > D1
Процесс применеия операции - шаг вычислений будем записывать: a1 -> A(a0) в общем виде и для случаев A= DN : a1 -> DN(a0). Например для деления на 3, это будет выглядеть как a1 -> D3(a0).
Введём понятие ранга делимости числа nn, так что n3 это ранг делимости на 3, n2 - соответственно, - на 2 и т.д. То есть если число a0 имеет n3=2 то оно делится на 9, а если у него ещё и n2=3 то оно делится и на 8 к тому же. Соответственно у простого числа a есть только два ранга na=1 и n1=var. Эти ранги есть у любого числа и говорить о них обычно нет смысла. Назовём их тривиальными и далее если не сказано специально, будем называть рангами только нетривиальные ранги. Так число имеющее только (нетривиальный) ранг n2 - это число представляющее из себя степень числа 2. Как уже доказано числа с единственным n2 не могут иметь n3 отличного от 0. То есть на 3 они делиться не могут (3 в степени 0 это 1 - то есть, - вырожденный до тривиального, случай).
Этот простой вывод пригодится в дальнейшем. Он важен в том смысле, что если у числа a0 n2>1 и n3>1 то рано или поздно придётся делить и на 2 и на 3 проводя операции независимо друг отдруга. Как будет видно, для n2=1 случай особый. Но - по порядку.
Если мы имеем a0 с n3>0 то ясно, что операция A=D3 лучший выбор, так как она старше всех (наиболее эффективна) и так как рано или поздно её всё равно придётся провести. Таким образом рекурсивно доказано, что любое исходное число превращается в число с n3=0 (не делимое на 3) минимальным количеством операций и все они A=D3.
Пусть a0 уже имеет n3=0. Это значит, что имеются лишь две возможности: A=D2 и A=D1. На первый взгляд кажется, что D2 если она возможна (n2>0) лучше, чем D1, но оказывается, это не всегда так. Это потому что D1 очень отличается от D3 и D2 тем, что её (D1) результат, в отличие от них изменяет признаки делимости на 2 и 3, влияя на применимость остальных операций (как мы видели ранее D2 и D3 не влияют на возможность проведения друг друга и тем более D1 которая возможна всегда). То есть, если n2=1 и мы проведём D2, то останется лишь D1 (мы оговорили, что a0 имеет n3=0). Итого начав с D2 мы обречены на последовательность D2, D1.
А вот если мы начнём с D1, то возможны случаи когда n3 станет n3>0. Тогда мы получаем возможность для пары D1, D3, которая эффективнее D2, D1. То есть, если n2=1, то следует проверить не делится ли на 3 результат D1(a0) и если это так, то выбирать D1, D3 вместо D2, D1.
Но если a0 имеет n3=0, а n2>1, то ситуация меняется. Пусть n2 = 2. Тогда если мы выберем D1, D3 (если он даже возможен), то очевидно проиграем варианту D2, D2 поскольку разделить на 4 это выгоднее чем уменьшить в 3 раза и вычесть 1.
То есть, если n2=2 и более, нужно разделить на 2 (D2), а потом проверить не понизилоь ли n2 до 1. То есть, пока n2>1 можно смело делить на 2 (D2,D2,D2...), а как только n2=1, то нужно поверять a1->D1(a0) на n3>0. Очевидно, что D1 применяется всегда, когда n2=n3=0.
Вот пожалуй и всё. Теперь легко написать условия для решения данной задачи (см. листинг).

3

Сообщение от AndreiUshakov Но без рекурсии ее тяжко решить

Эффективный алгоритм решение данной задачи уже предложили Байт и Новичок, а также стоит посмотреть на коды IGPIGP.

Насчёт рекурсии, вообще первое что приходит в голову при решение таких задач это организовать перебор и найти то что тебе нужно с помощью этого перебора, но ограничения большие и не дают так просто решить задачу поэтому можно написать рекурсию заметить закономерность в переборе и повторяющиеся шаги которые были уже вычислены уже не вычислять заново а просто взять из массива(массив как кеш для нашей рекурсии) значение и дальше уже то что тебе самому нужно сделать с этим значением то и делаешь. В данной задаче я не уверен что такой подход эффективен или даже применим

0

Сообщение от no swear также стоит посмотреть на коды IGPIGP.

Он ужасен. Но рекурсия там есть. Хотя, в моём случае, без неё можно обойтись циклом до достижения результата. Для очень больших массивов данных, это имеет смысл, наверное.

0

IGPIGP, Вы нашли

Сообщение от IGPIGP Он ужасен.

В любом случае можно научиться чему то новому

0

0

Мой интернет меня просто убивает. Эти слова явно лишние тут

Сообщение от no swear Вы нашли

Просто так к сведению чтобы никто не подумал иначе

0