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

if( (N+1) % 4)

А это где в условии?

код - это мое «кривое» решение

Я даже не понимаю, зачем там увеличивать?

Опционально вычти, дели, дели, дели, вычти

По идее здесь надо рекурсивно работать. Как-то так

long count(long number) {
  long cadd = 0;
  long csub = 0;
  if (number == 0) {
    return 0;
  } else if (number % 2 == 0) {
    return 1 + count(number / 2);
  } else {
    cadd = count(number + 1);
    csub = count(number - 1);
    if (cadd < csub) {
      return 1 + cadd;
    } else {
      return 1 + csub;
    }
  }
}

Некрасиво, зато наглядно. На современных машинах стека должно хватить.

(15-1) = 14 /2 = 7-1 = 6 / 2 = 3 - 1 = 2/2 = 1 - 1 = 0 это 7 операций (15+1) = 2^4 /2 /2 /2 /2 = 1-1 = 0 6 операций

Упс, действительно

Немного заменил

int count(int number) {
	int cadd = 0;
	int csub = 0;
	if (number < 3) {
		return number;
	} else if (number % 2 == 0) {
		return 1 + count(number / 2);
	} else {
		cadd = count(number + 1);
		csub = count(number - 1);
		if (cadd < csub) {
			return 1 + cadd;
		} else {
			return 1 + csub;
		}
	}
}

int на long замени. А то мало ли.

#include <stdio.h>

int main()
{
    unsigned int number, prev, substractions, divisions;
    float temp;

    scanf("%d", &number);

    for (substractions = 0; number; substractions++)
    {
        prev = number;
        number &= number - 1;
    }

    temp = (prev & -prev);
    divisions = (*(unsigned*)&temp >> 23) - 0x7F;

    printf("%d\n", substractions + divisions);
}

(Не работает для ноля.)

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

все равно непонятно, почему мое решение не прошло.

У тебя оптимизирован только один вариант, а рекурсия полный перебор решений делает.

Поспешил с кодом. answer+=3 явно какая-то преждевременная оптимизация

Но у ТС решение вполне годится, но ошибка для n=3 и всех n которые к нему сводятся в цикле.

Быстрофикс:

int ans = 0;
	if (n < 4) return n;
	while (n > 3) {
		if (n % 2){
			if ((n + 1) % 4){
				n--;
			}
			else
				n++;
		}
		else
			n /= 2;
		ans++;
	}
	return ans+n;

Битовый сдвиг вправо при чётности и декремент при нечетности, пока не доберемся до нуля. Меньше операций уж некуда. Не на C, но суть та же :)

#!/usr/bin/gawk -f
BEGIN{
  print V
  n = 0
  while (V>0) {
    if (V%2 == 0) { V/=2; n++ } else { V--; n++ }
  }
  print n " ops"
}

./iter.awk -v V=12345
12345
19 ops

Проверять чётность более чем одного младшего бита смысла нет, т.к. доступна операция деления только на два (ну или сдвига на один бит), а «цена» декремента и деления/сдвига одна и та же. Инкремент в решении вообще не нужен.

Потому что твоё решение неверно, что показывает автоматическая система проверки, например для числа 125.

иди читай тред. ответ 18 для 12345

Меньше операций уж некуда

Еще один клинический птушник в девеле, сколько же вас.

Поспешил с кодом. answer+=3 явно какая-то преждевременная оптимизация

ну да поспешил - писал сразу в тред, не проверяя :-)

Баг с «3» и переполнением(кстати у вас такой-же) подправил, но answer+=3 это не «преждевременная оптимизация» - это как раз ход алгоритма

int numops(unsigned long N) {
	int answer;
	answer=0;
	while(N) {
		if ((N&3)==3) { // xx11 - incr and shift twice
			N>>=2;
			if (N) N++;
			answer+=3;
		} else if (N&1) { // xx01 - decr and shift twice
			N--;
			answer++;
			if (N) {
				N>>=2;
				answer+=2;
			}
		} else {	// xxx0 - shift
			N>>=1;
			answer++;
		}
	}
	return answer;
}

Слона не заметил, да. Вот фикс:

  while (V > 0) {
    if ((V>3) && ((V+1)%4 == 0)) { V++; n++ }
    if (V%2 == 0) { V/=2; n++ } else { V--; n++ }
  }

(V>3) - будет выполняться каждую итерацию, помимо V > 0. Это очень плохо.

Кстати, если n=2^K1 + L2*2^K2 + ... + Lj*2^Kj (тут K1 - максимальная степень, а все Li = +-1)

и количество слагаемых минимально, то ответ j + K1

тогда можно написать такую наркоманскую рекурсию

import sys
import math

power_of_2 = [2**i for i in range(22)]


def magic(n, is_first=False):
    k = int(math.log(n, 2))
    if n <= 2:
        if is_first:
            return n
        else:
            return 1
    elif n == power_of_2[k]:
        if is_first:
            return k + 1
        else:
            return 1
    else:
        res1 = magic(n - power_of_2[k])
        res2 = magic(power_of_2[k+1] - n)
        if res1 <= res2:
            if is_first:
                return k + res1 + 1
            else:
                return res1 + 1
        else:
            if is_first:
                return k + res2 + 2
            else:
                return res2 + 1

if __name__ == "__main__":
    print magic(int(sys.argv[1]), is_first=True)

Работает в два раза медленнее чем

def magic(n):
    if n <= 3:
        return n
    elif n % 2 == 0:
        return magic(n/2) + 1
    else:
        return min(magic(n-1), magic(n+1)) + 1

ты явно не понимаешь сути acm

(V>3) - будет выполняться каждую итерацию, помимо V > 0. Это очень плохо.

Таких нюансов в условии не было. Но и этому горю можно помочь:

  while (V > 3) {
    if ((V+1)%4 == 0) { V++; n++ }
    if (V%2 == 0) { V/=2; n++ } else { V--; n++ }
  }
  while (V > 0) {
    if (V%2 == 0) { V/=2; n++ } else { V--; n++ }
  }

Сравнение для тебя не операция?

Ну и второй вайл не нужен совсем, так как n = n + V для V = 0, 1, 2

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

Чтобы быстрее работало и как можно больше (не обязательно все) тестов проходило.

Ты про эту суть?

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

почти идеальное с моей точки зрение решение

на самом деле - это решение «в лоб». Учитывая, что задачка олимпиадная она делается чуток по другому. Ответ = сумма значащих бит+кол-во последовательностей из 1 бит и какой-то нюанс. Вот этот нюанс я не осилил :-(

Только не количество значащих бит, а позиция старшего. Нюанс = 1, если два старших бита единицы, иначе 0.

Однако кодом - аккуратный самоочевидный однопроходный простой конечно-автоматный разбор битовой строки.

Где ошибка?

нет ошибки. Всё правильно. Работает. В смысле — код работает, но это не решение.

Если тебе интересно решение, то оно простое: дели на 2. Если нельзя делить, вычитай 1.

на самом деле - это решение «в лоб». Учитывая, что задачка олимпиадная она делается чуток по другому. Ответ = сумма значащих бит+кол-во последовательностей из 1 бит и какой-то нюанс. Вот этот нюанс я не осилил :-(

эта задачка решается в лоб, делением пополам. Просто вы, туполобые, не знаете про деление с остатком, потому для вас сказано про «вычитание 1».

На самом деле, просто тупо делим пополам, и всё. Т.е. вот код:

while(n/=2);

можно посчитать счётчиком число этих «делений» (на самом деле — число сдвигов)

Можно вторым счётчиком посчитать число «вычитаний»:

count1 = count2 = 0;
do{
  count1++;
  count2 += (n&1);
}while(n/=2);

Батти-то ещё тупее чем казался до этого.

угу. У меня есть рабочий код и рабочее решение. А у тебя — только словоблудие. Даже такую простую задачку ты не смог осилить.

(2/2)-1=0 :)

угу. У меня есть рабочий код и рабочее решение.

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

Твой код - нерабочий. Он выдаёт некорректный ответ для 12345. Потому что ты старый тупой маразматик с кашей вместо мозгов.

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

Приведённый сниппет даёт ошибки на тестах

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

в каких тестах у меня ошибка?

Твой код - нерабочий. Он выдаёт некорректный ответ для 12345.

для 12345 нужно 14 операций сдвига. При этом, если «деление нечётных» по условию у меня получается как вычитание+деление, то число вычитаний равно числу единичных битов. Т.е. в среднем для 12345 == 7 log2(12345)/2. В данном случае нам повезло, и нужно всего 6 вычитаний. Т.е. всего

6 вычитаний
14 сдвигов

ты сделал лучше?

см выше: число сдвигов равно log2(n), число вычитаний в среднем равно log2(n)/2. Аналитически число вычитаний можно представить как сумму остатков от деления n на 2^m для m=0..log2(n).

Если число четное - делим на два.

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

Иначе отнимаем 1.

в каких тестах у меня ошибка?

уже очевидно, что не в тестах - в коде..генетическом

вы так и не прочли условие задачи :-)

можно даже аналитически доказать, что «мой» метод самый быстрый:

Понятно, что деление пополам сходится быстрее к нулю, чем вычитание. Потому нам нужно ВСЕГДА делить. Но всегда нам не дают. Значит мы должны применять инкремент или декремент. И то и другое надо применить всего один раз, но декремент нужен, ибо приближает нас к нулю, а декремент — только удаляет. Ибо ((2*n+1)+1)/2 > ((2*n+1)-1)/2.

Следовательно, нам нужно всегда делить пополам, а если это невозможно, использовать декремент перед делением. Других вариантов нет.

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

и смысл? Ведь после прибавления 1 нам придётся два раза делить на 2. Или в условии разрешено делить на 4? Я что-то этого не наблюдаю.

И даже если и наблюдаю, то что ты скажешь про цену операции если число+1 делится на 4? Она по твоему бесплатная?

А мне вот кажется, что на amd64 быстрее будет моим методом пользоваться, и делить на 2 даже тогда, когда можно делить на 4. Ибо цена лишнего сдвига куда меньше, чем цена лишней проверки &3 и плюс цена условного перехода.

декремент нужен, ибо приближает нас к нулю

Хинт: деление приближает быстрее

Разберём 15.
Твой способ:
1: -1 = 14
2: /2 = 7
3: -1 = 6
4: /2 = 3
5: -1 = 2
6: /2 = 1
7: -1 = 0
Семь шагов.
Правильный алгоритм:
1: +1 = 16
2: /2 = 8
3: /2 = 4
4: /2 = 2
5: /2 = 1
6: -1 = 0
Шесть шагов.

Разобрать 65535 обоими способами оставляю для домашнего задания.

вы так и не прочли условие задачи :-)

вот это:

Дано целое неотрицательное число. С ним можно делать следующие операции: увеличивать на 1; уменьшать на 1; делить его на два, если оно четное. Требуется за минимальное число операций получить 0. Вход. Целое неотрицательное число меньше 2000000.

Это я прочитал. Может тут между строчек ещё что-то незамеченное? Или я какие-то слова не так понимаю? Дык я жеж в школу 20 лет назад окончил, могу и спутать что-то...

Чего так много букв то?

#!/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 not (x+1)%4 else x-1, count+1
    print count, ':', x

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

В задаче ТС ни слова не сказано о том, что проверки условий и пр. считаются операциями. Можно считать, что преобразования числа просто модель для какого то достаточно дорого процесса.

И всегда лучше два раза поделить на два, если есть возможность. Иначе представьте, как адово будет выглядеть цепочка для 2^n-1 ;-)

Разберём 15.

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

А вот теперь возьми, и проверь, сколько процентов ты от этого выиграешь для чисел от 1 до 200 000.

Хинт: деление приближает быстрее

угу. Именно оно и занимает большую часть времени, ибо делить придётся по любому.

Фишка в том, что уменьшая число единиц ты уменьшаешь число вычитаний, и увеличиваешь число делений.

Тут ошибка в условии, как при анализе демона Максвелла — проверка делимости на 4 у вас почему-то «бесплатная», хотя на самом деле, она не только достаточно дорогая, но и на x86/amd64 НАМНОГО дороже сдвига и декремента.

Кроме того, в условии задачи, такой операции «проверка остатка от деления на 4» нету.

Чего так много букв то?

На арифметике любой дурак сможет. А я на строках :) Кстати, ты забыл про патч для 3 и всех остальных 110*b

В задаче ТС ни слова не сказано о том, что проверки условий и пр. считаются операциями.

вот потому-то и ВУЗы выпускают говнокодеров, которые считают инкремент — операцией, а вот «поделить на 4 с остатком, и проверить равенства остатка 3» — «не операцией».

В таком случае я могу и такой алгоритм написать, с НУЛЁМ операций:

проверить и запомнить ВСЕ варианты
выбрать самый короткий вариант
распечатать число операций для самого короткого варианта

разве в этом «алгоритме» есть хоть одна операция?

Можно считать, что преобразования числа просто модель для какого то достаточно дорого процесса.

нельзя. Потому-что в твоих «проверках» неявно сами числа используются. Т.е. если у тебя операции дорогие, то и проверки будут такими же.

И всегда лучше два раза поделить на два, если есть возможность. Иначе представьте, как адово будет выглядеть цепочка для 2^n-1

мне это только-что продемонстрировали. При этом сами проверки конечно были «спрятаны», код аффтор предоставить постеснялся.