Задача «Число операций»

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

Это Вы себе сами придумали. Потому что нигде не сказано, что я поеду по предложенному маршруту.

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

дык на ошибки-то укажите?

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

emulek утвердает, что ему за 30. Как-то слабо верится.

а то!

в общем-то формально задачу можно трактовать таким образом

ох... Ну наконец-то.

но тогда она не несёт никакого смысла, т.к. превращается в элементарную для всех.

она и в вашем списочном смысле не слишком сложна.

она и в вашем списочном смысле не слишком сложна.

в этом случае она не решается устно, или решается, но не очевидно, во всяком случае, что попрограммировать есть.

P.S. мне действительно интересно существуют ли случаи, когда плюс может быть в середине операции, поидее должны существовать, но придумать пример мне не удалось.

Задача - найти минимальное число операций ++, --, /2 для превращения x в ноль. Нигде не сказано, что при этом должно учитываться число операций в каких то промежуточных вычислениях, проверках и пр., но Вы их упорно пытаетеся зачем то учитывать.

Если бы задача была - найти за минимальное число операций способ превратить x в ноль при помощи {++, --, /2}, то ответ был бы - «x раз --» (способ найден за одну операцию без всяких проверок, профит!).

Пытаться найти оптимальный способ превращения x в ноль при помощи {++, --, /2} с учетом времени на проверки и какие то операции по анализу x бессмысленно, потому что для построения целевой функции нужно знать с каким весом входят операции {++, --, /2} над х с и с каким весом входят операции по анализу х и всякие проверки. Как правило такая задача не ставиться.

Так что чем быстрее Вы посыпете голову пеплом, тем быстрее Вы перестанете выглядеть клоуном в глазах присутствующих.

P.S. мне действительно интересно существуют ли случаи, когда плюс может быть в середине операции, поидее должны существовать, но придумать пример мне не удалось.

В смысле? 11100? /2/2+1/2/2/2-1?

Дарю!

!/usr/bin/sh
echo 0

Тоже хотел написать это как решение задачи в понимании emulek :D

Точнее даже

echo 0

sh в /bin/sh у меня, но его моно и не указывать;-)

мой вариант не спотыкается

Да ну? Твой вариант превращает 15 в 0 за 7 шагов, мой — за 6 (Задача «Число операций» (комментарий)). Не надо быть даже первоклассником, чтобы найти из этих чисел меньшее.

алгоритм в студию

Задача «Число операций» (комментарий)

Если с перловым синтаксисом проблемы, ты спрашивай, не стесняйся.

да, спасибо.

P.S. мне действительно интересно существуют ли случаи, когда плюс может быть в середине операции, поидее должны существовать, но придумать пример мне не удалось.

? Для любого N = 2^k(2^l-1) будет { /2 × k, +, /2 × l }

не подходит же, ему нужно написать решение на ассемлберноподобном языке, где типы это Int и есть операции:

PLUS     %reg       -- +1
MINUS    %reg       -- -1
MOD2     %ref %addr -- /2 или прыжок на %addr если деление невозможно
ISZERO   %reg %addr1 %addr2 -- в зависимости от результата прыжок на addr1 или addr2
EXIT     -- выход

+ всякие операции типа положить в регистр и т.п.

и какая-то программа вида

 
10: ISZERO %a 20 100
20: MOD2  %a 30
30: MINUS %a
40: GOTO 10
100: EXIT

все правильно сказал.

Меня другое умиляет, почему в задаче ТС проверки в условиях не считаются операциями?;-)

тебе тоже стоит уменьшить свое чсв и взглянуть внимательней на код.

Забавный тред: тс нужно было подсказать про n==3, предложить более оптимизированный вариант, спасибо MKuznetsov. Но тред скатился в срач не только из-за непонимая сути acm, но и не умения правильно читать корявые тексты.

Ждем новых задачек от ТС и бурных обсуждений.

ему нужно написать решение на ассемлберноподобном языке

Их есть у меня!

        .file   "test.cpp"
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "0"
        .section        .text.startup,"ax",@progbits
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB12:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $.LC0, %edi
        call    puts
        xorl    %eax, %eax
        addq    $8, %rsp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE12:
        .size   main, .-main
        .ident  "GCC: (Debian 4.7.2-5) 4.7.2"
        .section        .note.GNU-stack,"",@progbits

тебе тоже стоит уменьшить свое чсв и взглянуть внимательней на код.

Для просмотра мне хватает кода от своих студентов.

Как-то слабо верится.

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

Условия в задаче достаточно чёткие

Таки буду препираться :) Вот это: «С ним можно делать следующие операции» - ни как не выделено, что это относится только к описанию задачи, а не к ограничениям на алгоритм. Для меня это «прозвучало» аналогично «Пользоваться калькулятором на экзамене запрещено» :)

вместо того чтоб препираться, решил-бы задачу в том виде каком понял :-) Надеюсь циклы в вашем понимании допустимы ?

int numops(unsigned long long N) {
	int answer;
	answer=0;
	while(N>3) {
		if (N&1) {
			N--;
			if (N) {
				N>>=1;
				answer++;
				if (N&1) N++;
			}
		} else {
			N>>=1;
		}
		answer++;
	}
	return answer+N;
}

бедные студенты;-) препод копипастит asm код c-программы

в этом случае она не решается устно, или решается, но не очевидно, во всяком случае, что попрограммировать есть.

ИМХО решение очевидно...

мне действительно интересно существуют ли случаи, когда плюс может быть в середине операции, поидее должны существовать, но придумать пример мне не удалось.

14 попробуй. Это чётное. Минимальное нечётное очевидно 29.

29-1=28
28/2=14
14/2=7
7+1=8
8/2=4
4/2=2
2/2=1
1-1=0

а предыдущий вариант с n+=3?

Задача - найти минимальное число операций ++, --, /2 для превращения x в ноль. Нигде не сказано, что при этом должно учитываться число операций в каких то промежуточных вычислениях, проверках и пр., но Вы их упорно пытаетеся зачем то учитывать.

просто для ответа на этот вопрос, необходимо, что-бы число на входе было ЗАРАНЕЕ ИЗВЕСТНО. Вот вы почему-то думаете, что это так. Что его можно «записать в виде битов и посмотреть». А я — не думаю. Я просто применяю заданные в условии операции.

Пытаться найти оптимальный способ превращения x в ноль при помощи {++, --, /2} с учетом времени на проверки и какие то операции по анализу x бессмысленно, потому что для построения целевой функции нужно знать с каким весом входят операции {++, --, /2} над х с и с каким весом входят операции по анализу х и всякие проверки.

ну раз вес не задан, значит он равен 1. Т.е. все операции одинаковы.

Как правило такая задача не ставиться.

но в первом посте именно такая задача и поставлена.

Так что чем быстрее Вы посыпете голову пеплом, тем быстрее Вы перестанете выглядеть клоуном в глазах присутствующих.

да мне пофиг, что вы про меня думаете. Давайте ваш алгоритм, обсудим. Я свой уже дал. А от вас — только бла-бла-бла. Типа «для 15 твой алгоритм неправильный, потому-что я угадал, что можно сначала прибавить, и тогда вычитать не нужно!». Т.е. ваш алгоритм построен на догадках. Ну или на подборе.

И это не удивительно, ибо если вы его формализуете, то вам придётся признать, что операций таки больше получается. Увы.

таких операций не определено в условии. Продолжаем клоунаду?

мой — за 6

твой основывается на догадках.

Если с перловым синтаксисом проблемы, ты спрашивай, не стесняйся.

да. Как эти операции реализовать в пространстве операций, заданном в условии задачи?

пред.вариант эффективней и понятнее. А этот просто демонстрирует возможность корректного решения с ограничениями на применяемые операции; то есть то что некоторые теоретики и знатоки фразеологии в этом треде не осиливают.

просто для ответа на этот вопрос, необходимо, что-бы число на входе было ЗАРАНЕЕ ИЗВЕСТНО. Вот вы почему-то думаете, что это так. Что его можно «записать в виде битов и посмотреть». А я — не думаю. Я просто применяю заданные в условии операции.

Это фраза в стиле Царя - такой же феерический бред.

ну раз вес не задан, значит он равен 1. Т.е. все операции одинаковы.

Это Вы себе нафантазировали.

но в первом посте именно такая задача и поставлена.

И это тоже сугубо Ваши фантазии.

Давайте ваш алгоритм, обсудим.

Задача «Число операций» (комментарий) Задача «Число операций» (комментарий)

от вас — только бла-бла-бла.
да мне пофиг, что вы про меня думаете

Я про Вас ничего уже не думаю, кроме того что бы добавить Вас в свой игнор лист. Подожду еще один пост от Вас, вдруг таки начнете себя вести нормально... верю в чудеса.

Я не пишу на асме, g++ это делает лучше меня.

из-за непонимая сути acm

уважаемый, может объясните эту суть, или лучше дадите ссылку?

Как эти операции реализовать в пространстве операций, заданном в условии задачи?

Деление на 2:
$s =~ s/0$//;
Вычитание единицы:
$s =~ s/01$/00/;
Добавление единицы с одновременным делением на 2 максимально возможное число раз:
$s =~ s/(0?)(1+)$/1/;

Больше операций над входными данными не производится, остальное — управляющие конструкции.

ненене дэвид блэйн, я тебя не кормлю. Но в треде уже написал, скролли вверх

просто для ответа на этот вопрос, необходимо, что-бы число на входе было ЗАРАНЕЕ ИЗВЕСТНО. Вот вы почему-то думаете, что это так. Что его можно «записать в виде битов и посмотреть». А я — не думаю. Я просто применяю заданные в условии операции.

Это фраза в стиле Царя - такой же феерический бред.

т.е. возразить вы не в состоянии?

ну раз вес не задан, значит он равен 1. Т.е. все операции одинаковы.

Это Вы себе нафантазировали.

вопрос был о «минимальном числе операций», с чего я должен считать, что одни операции дороже других?

Если число четное - делим на два. Если число нечетное и при прибавлении 1 делится на четыре - прибавляем 1.Иначе отнимаем 1.

операция деления на 4 не определена. Какое вы имеете право её использовать? Откуда вы знаете, что она даст правильный результат?

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

Ваше решение конечно имеет право на существование (ну в смысле, что вы _можете_ додумать всё это), но далеко не факт, что оно будет оптимальным.

Как этот алгоритм будет работать IRL? Вот на входе число 15, как он(алгоритм) будет определять, что надо 15+1? Отправлять запрос на сервер, который умеет делить на 4 с остатком? По вашему это «оптимально»?

Я про Вас ничего уже не думаю, кроме того что бы добавить Вас в свой игнор лист. Подожду еще один пост от Вас, вдруг таки начнете себя вести нормально... верю в чудеса.

попытайтесь описать реализацию своего «алгоритма» в железе, а не в фантазиях. Я вот реализацию не представляю.

Добавление единицы с одновременным делением на 2 максимально возможное число раз

что-то в первом посте я такой операции не видел.

ненене дэвид блэйн, я тебя не кормлю. Но в треде уже написал, скролли вверх

я видел, но не понял. Объясни для тупого. Что за такая «суть acm»?

Citius, Altius, Fortius!

неправильно для: 3, 6, 11,12,13,22,23,24,25,26...

в общем для всего, что через 3-ку идёт.

избавиться от сравнения N>3

заменить N>3 на 1, добавить в одно сравнение N!=1, добавить условный «бряк» - и получим чистый answer )

Только всё равно задача сформулирована криво! :-Р

Citius, Altius, Fortius!

ладно. Закончим спор, я упоролся, и уже НИЧЕГО не понимаю. Я думал, это девиз олимпиады. В контексте нашего спора, для меня загадка, что значит «Altius, Fortius», и почему ВНЕЗАПНО мне выше сказали, что «твоё „быстрее“ никому здесь не интересно».

ответ должен быть правильным. неправильные ответы никому не нужны.

Может ты ещё и подпрограммы не используешь, каждый раз printf реализуя с нуля на машинных кодах? Можно прибавлять, можно делить => можно добавлять и делить в рамках одной подпрограммы.

ответ должен быть правильным. неправильные ответы никому не нужны.

к сожалению, жизнь != олимпиада. В жизни побеждает обычно не тот, кто дальше плюнет, а тот, кому во первых повезёт, а во вторых — кто знает, когда и куда плевать. А вот доплюнет или нет — это уже третий вопрос. И обычно он значения не имеет, если первые два условия выполнены.

Если ты до сих пор не понял, то дело не в этой задаче, а в самом определении понятия «правильный ответ». А как сама задача решается — я в курсе.

ну собственно вот до тебя и не допетривает, что никто не заморачивается в правильных формулировках, а ответ извольте дать правильным. Вот ти и проиграл по жизни. Засрал тред кучей сообщений по ПРОСТОЙ задачке. Эта задачка для 6 класса

Может ты ещё и подпрограммы не используешь, каждый раз printf реализуя с нуля на машинных кодах?

нет конечно. Хотя один раз мне пришлось так сделать, потому-что я писал тест памяти, и естественно не мог юзать эту самую память(в т.ч. и для стека вызовов). Надо сказать — задолбался делать...

Можно прибавлять, можно делить => можно добавлять и делить в рамках одной подпрограммы.

конечно можно. Вот только изначально вопрос стоял «реализовать минимальным количеством ЭТИХ операций». Дебилу понятно, что выдать ноль на выходе можно и без этих операций, если есть другие. Я уже выше написал:

XOR EAX, EAX

#!/usr/bin/python
import sys
count, x = 0, int(sys.argv[1])
while x: 
    x, count = x/2 if not x%2 else x-1 if (x+1)%4 or x==3 else x+1, count+1
    print count, ':', x

Тройка выделенный случай? Ну ок, лень думать.

для тройки --- выгоднее, чем +/--. Ок, щас эту сравню.

т.е. возразить вы не в состоянии?

Это будет неконструктивно. Я Вам попытался объяснить, откуда такие задачи берутся, но видимо моих преподавательских навков для этого недостаточно. По остальным пунктам аналогично - с моей точки зрения Вы с упоением несете феерический бред.

Бай.

ну собственно вот до тебя и не допетривает, что никто не заморачивается в правильных формулировках, а ответ извольте дать правильным. Вот ти и проиграл по жизни. Засрал тред кучей сообщений по ПРОСТОЙ задачке. Эта задачка для 6 класса

мне что больше всего нравится в этом треде, так это то, что никто так до сих пор и не дал вменяемого решения ЭТОЙ задачи.

Пока победителем можно признать только код из первого поста, хотя он и с ошибкой. (: Ну и не выдаёт он решения. Только число операций(неправильно).

если ты слепой и не видел кучи кода, то это твои проблемы. Чуть позже выкину результат тестов сравнения

x, count = x/2 if not x%2 else x-1 if (x+1)%4 or x==3 else x+1, count+1

это ты специально в одну строку пишешь?