тащем-то я только ваш код наблюдаю.

ссылку дал на мои небольшие правки (polish) чужого кода.

Проверять его мне лениво.

естественно. Тебе даже свой код лень проверить :-) Точнее квалификации нехватает. Не отчаивайся - ещё лет 10 и возможно будет легче

обучение дятлов программированию выходит за рамки треда, варианты решений ТС`у предложены, лоботомия на форуме запрещена

засим /thread

Педик, тебя спрашивали за минимум множества ЗНАЧЕНИЙ. Аккурат как в исходной задаче. Найти минимцум из -1, 0, 1 уже не можешь, сын проститутки?

Михаил, в чём твоя проблема, и что ты хочешь до меня донести?

Баття, до тебя пытаются донести, что ты тупой. Исходная задача поставлена абсолютно корректно: на каждое число из диапазона [0 .. 200000] надо найти такое число, которое являлось бы длиной минимальной последовательности операций, приводящих исходное число в 0. Для каждого из чисел есть бесконечное количество таких последовательностей, и бесконечное множество длин этих последовательностей, но у этого множества есть МИНИМУМ. Тебе это строго доказать, или уже и так дошло?

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

естественно. Тебе даже свой код лень проверить :-) Точнее квалификации нехватает

тебе тоже не хватает. Иначе-бы не пи**л, а просто указал-бы на ошибку. Но этого ты не можешь. Как и свой код написать. Даже имея готовый алгоритм: Задача «Число операций» (комментарий) Я-то по своему делал...

Ну и ещё раз повторю: в любом случае это решение не является верным. Только в ваших фантазиях.

Исходная задача поставлена абсолютно корректно: на каждое число из диапазона [0 .. 200000] надо найти такое число, которое являлось бы длиной минимальной последовательности операций, приводящих исходное число в 0

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

А та, что ты поставил — не имеет смысла. Если-бы в первом посте было-бы так написано, я-бы вообще ничего не написал, ну максимум послал-бы ТСа подальше.

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

интересное предложение.

Нет, сын проститутки, исходная задача ставится именно так, как я переписал, и в такой формулировке всегда имеет однозначное и конкретное решение.

Вход. Целое неотрицательное число меньше 2000000.

Выход. Минимальное число операций.

Сравни с:

на каждое число из диапазона [0 .. 200000] надо найти такое число, которое являлось бы длиной минимальной последовательности операций, приводящих исходное число в 0

У меня более многословно (чтоб даже такое ничтожество, как ты, смогло понять), но смысл абсолютно тот же самый.

учись читать:

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

И да, ничтожество:

С ним можно делать следующие операции:

Вдумайся в смысл этой фразы.

Ты, сын шлюхи-наркоманки, явный дислексик. Читай внимательно, сучка:

Дано целое неотрицательное число. С ним можно делать следующие операции: увеличивать на 1; уменьшать на 1; делить его на два, если оно четное. Требуется за минимальное число операций получить 0. Вход. Целое неотрицательное число меньше 2000000. Выход. Минимальное число операций ДЛЯ ДАННОГО ЧИСЛА.

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

Минимальное число операций ДЛЯ ДАННОГО ЧИСЛА.

Михаил, никто ещё не смог построить алгоритм, который работает БЕЗ числа (кроме меня, но мой алгоритм не понравился). ВСЕ выше описанные алгоритмы(все два) требуют ОПЕРАЦИЙ над ДАННЫМ числом, причём МНОГО операций. Эти операции для построения алгоритма никто не считает, ибо «их нет в условии». А их — и в правду там нет. И считать их вправду нельзя, как и вообще применять. Потому НЕВОЗМОЖНО построить алгоритм, который вычисляет последовательность операций без самого этого числа. А то, что тут было == типичное деление на ноль: берём число, смотрим какие нужно делать операции, для этого выполняем эти опреации, а потом выполняем ещё эти операции. Но считаем только те операции, которые были выполнены после некоторой границы, которую сам же и придумали. Т.е. пробуем прибавить/вычесть, узнаём, ЧТО надо делать для ЭТОГО числа, а ПОТОМ уже делаем.

Т.е. сами додумываем правила, и успешно делим на ноль, получая бесконечность. Потому-что додумали, что «по правилу Лопиталя ноль всегда больше нуля, но маленький, а emulek просто дурак, и ваще мы самые умные».

Ах да, в списке операций нет сравнения! шок сенсация видео! В том числе с нулем! Исходя из этого задача нереш^W^Wнам не нужны 4 предыдущие операции! Выводим 27 и не паримся!

Они просто завидуют гению.txt

Ах да, в списке операций нет сравнения!

есть. Прочитай ещё раз.

нельзя в одной консольке запустить программу с редиректом в файл, а в другой смотреть.

Для этого hFlush нужен:

forM_ [1 .. 2000000] $
  \i -> do
    -- 1.
    putStrLn $ printf "%i %i" i $ findnum i
    -- 2.
    printf "%i %i\n" i $ findnum i
    -- 3.
    B.hPutBuilder stdout $
      B.intDec i <> B.byteString " " <> B.intDec (findnum i) <> B.byteString "\n"
    -- !
    hFlush stdout

З.Ы. Вообще есть рекуррентное соотношение — http://oeis.org/A061339, гораздо быстрее чем полный обход получается.

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

билдеры это круто, но putStrLn достаточно в решении на поржать достаточно. Использовать рекурентное отношение или вариант как тут сишники пишут естественно эффективнее.

Либо hSetBuffering stdout LineBuffering в начале main, правда

гораздо быстрее чем полный обход получается

Настолько, что это уже не важно :)

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

если оно четное

это по твоему что?

То есть ты считаешь что x%2==0, x==y, x!=y, x>y, x<y тождественны?

нет. Я так не считаю. Ещё вопросы, мой укуренный друг?

Вот аналогично сишному варианту:

import Data.Function
import Data.Vector.Unboxed.Mutable as V
import Text.Printf
import Control.Monad

main :: IO ()
main = do

{-
  let
    f 0 = 0
    f 1 = 1
    f n = let (d, m) = n `divMod` 2 in
      if m == 0 then f d + 1 else min (f d + 2) (f (d + 1) + 2)
-}

  mem :: IOVector Int <- V.replicate 2000000 0
  unsafeWrite mem 1 1

  let

    wrt arr ix val = unsafeWrite arr ix val >> return val

    f n = do
      e <- unsafeRead mem n
      if e > 0
      then return e
      else do
        let (d, m) = n `divMod` 2
        if m == 0
        then wrt mem n . (+1) =<< f d
        else wrt mem n =<< liftM2 (min `on` (+2)) (f d) (f (d + 1))
        --                 (min `on` (+2)) <$> f d <*> f (d + 1)
  forM_ [1 .. 1000000] $ \i -> printf "%i %i\n" i =<< f i

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

Russian, motherfucker, do u speak it? СРАВНЕНИЕ и ПРОВЕРКА НА ЧЕТНОСТЬ это одно и то же? Если я тебя правильно понял, ты так не считаешь. С другой стороны, на реквест операции сравнения в условии ты ответил проверкой на четность. Может они выводятся неизвестным мне способом друг из друга? Пока все.

Хотя, предположу, что «укуренный друг» это некто, чьи посты на форуме ты способен увидеть только в состоянии наркотического опьянения, с твоими-то трактовками. Не стоит подтверждать или опровергать эту гипотезу, сомневаюсь, что он это оценит.

очевидно можно и дальше подсокращать - но лень ;-)

вот:

int numops(int N) {
	return N&1 ? (--N ? ((N>>=1)&1 && (N-1) ? numops(N+1) : numops(N))+2 : numops(N)+1) : (N ? numops(N>>1)+1 : 0);
}

для ряда 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

очевидно ответы

0,1,2,3,3,4,4,5,4,5,5,6,5,6,6,6,5

т.е. для 2**к число действий к+1 , наиболее дорогие числа нечетные («долгой» нечётности) «равноудалённые от степеней двойки(самых дешёвых чисел)

f(2*n)=f(n)+1

для n>0 f(2*n+1)= min(f(n),f(n+1))+1

это поймается после вычитания (1 операция) и деления (1) операция и добавления(1 операция ) всего 3 операции , что тоже самое что добавить дважды и один раз поделить

С чего 7 страниц?

Лисперы были, позорно слили? Бомбануло, ошмётки пердаков разлетелись? just as planned?

Не, не лисперы. Дегенераты какие-то были, предлагали нерабочие алкоритмы. Хотя... ну как были... были да остались.

Версия без оптимизации, зато с дебагом:

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
	if(argc != 2){
		puts("?");
		return 1;
	}
	unsigned int count = 0, num = atoi(argv[1]);
	printf("num: %d\n", num);
	while(num != 0){
		if(num%2 == 0){
			num/=2;
			printf("[D]%d\n", num);
			count++;
		} else {
			num--;
			printf("[D]%d\n", num);
			count++;
		}
	}
	printf("count: %d\n", count);
	return 0;
}

Пальмой по фейсу. Тебя Др.Батти покусал?
Задача «Число операций» (комментарий)

Приписки тоже читать надобно - там наколенная без оптимизаций.

Что значит «без оптимизаций»? Она просто даёт неправильный ответ. Тут хоть заоптимизируйся.

Похоже ты прав, удаляюсь читать мануалы и Кернигана

just as planned

(defun count-something (number &optional prev flag)
  (if (= number 1)
      1
      (if (oddp number)
          (if flag
              (+ 1 (count-something (floor number 2) t t))
              (if prev
                  (+ 2 (count-something (floor number 2) t t))
                  (+ 2 (count-something (floor number 2) t nil))))
          (+ 1 (count-something (floor number 2) nil nil)))))

(defun count-something (number &optional prev flag)
  (if (= number 1)
      1
      (if (oddp number)
          (if flag
              (+ 1 (count-something (floor number 2) t t))
              (if prev
                  (+ 2 (count-something (floor number 2) t t))
                  (+ 2 (count-something (floor number 2) t nil))))
          (if flag
              (+ 1 (count-something (floor number 2) t nil))
              (+ 1 (count-something (floor number 2) nil nil))))))

Нужно больше скобочек!

на лиспе так не пишут - повокация не удалась, да и код не верный

Нужно больше скобочек и хвостовой рекурсии

(defun 2/ (number)
  (if (oddp number)
      (error "2/: Number is odd")
      (/ number 2)))

(defun apply-count (number count)
  (reduce (lambda (num fun)
            (funcall (symbol-function fun) num))
          count :initial-value number))

(defun count-something (number &optional prev flag result)
  (if (= number 1)
      (nreverse (cons '1- result))
      (if (oddp number)
          (if flag
              (count-something (floor number 2) t t (cons '2/ result))
              (if prev
                  (count-something (floor number 2)
                                   t t
                                   (append (list '2/ '2/ '2/ '1+)
                                           (cddr result)))
                  (count-something (floor number 2) t nil
                                   (append (list '2/ '1-)
                                           result))))
          (if flag
              (count-something (floor number 2) t nil
                               (append (list '2/ '1-) (cdr result)))
              (count-something (floor number 2) nil nil
                               (cons '2/ result))))))

повторяю для особо тупых:

ты похапешник-дебил с нерабочим кодом

Нужно больше жыра

Этот алгоритм не то что на PHP, его ни на каком другом языке реализовать нельзя. Где еще кроме Лиспа есть макросы, CLOS, MOP, CMYK и SICP?

Чё за набор баззвордов?

(defun test (num)
   (let ((min #.most-positive-fixnum))
     (labels ((int (num op-counter)
		(if (= 1 num)
		    (setf min (min (1+ op-counter) min))
		    (if (evenp num)
			(int (/ num 2)(1+ op-counter))
			(progn (int (1- num) (1+ op-counter))
			       (int (1+ num) (1+ op-counter)))))))
      (int num 0))
     min))

Как говаривал отец лиспа Моисей Эльевич Шейнфинкель: "...premature optimization is the root of all evil".

(defun recursive-count (number)
  (if (= number 1)
      1
      (if (evenp number)
          (1+ (recursive-count (/ number 2)))
          (1+ (min (recursive-count (1+ number))
                   (recursive-count (1- number)))))))

(c)

Прочитал.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]){
	if(argc != 2){
		puts("?");
		return 1;
	}
	unsigned int count = 0, num = atoi(argv[1]);
	unsigned int temp = 0, count2 = 0, num2 = num;
//	printf("[D] num: %d\n", num);
	while(num != 0){
		if(num%2 == 0){
			num/=2;
//			printf("[D] %d\n", num);
			count++;
		} else {
			num--;
//			printf("[D] %d\n", num);
			count++;
		}
	}
	while(num2 != 0){
		if(num2%2 == 0){
			num2/=2;
//			printf("[D] %d\n", num2);
			count2++;
		} else {
			if(temp==0){
				num2++;
			} else {
				num2--;
			}
//			printf("[D] %d\n", num2);
			count2++;
			temp = 1;
		}
	}
	if(count <= count2){
		printf("%d\n", count);
	} else {
		printf("%d\n", count2);
	}
	return 0;
}

elemashine@laptop:~/Work$ perl -e 'for($i=1;$i<=50;$i++){system("./a.out $i");}'
1
2
3
3
4
4
5
4
5
5
6
5
6
6
6
5
6
6
7
6
7
7
7
6
7
7
8
7
8
7
7
6
7
7
8
7
8
8
8
7
8
8
9
8
9
8
8
7
8
8

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

Вот решение

#!/bin/bash
read chislo
echo "0"

И да, напишите кто-нибудь правильную версию на Си

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

СРАВНЕНИЕ и ПРОВЕРКА НА ЧЕТНОСТЬ это одно и то же? Если я тебя правильно понял, ты так не считаешь. С другой стороны, на реквест операции сравнения в условии ты ответил проверкой на четность.

реквест был в «проверках». А проверка на ноль сама собой очевидна, ибо в условии сказано: «за минимальное число операций получить 0». Как можно «получить 0» без проверки, «получился-ли ноль?» ? Очевидно, если такая проверка неопределена, алгоритм будет работать бесконечно, даже если он и получает нуль(и).

зачем мне? Там, ближе к началу, уже был мой код для x86

xor ax,ax

твой тоже был.

Логика простая - для 1 операция, очевидно, одна, для 2 — две, для 3 — три, любое число больше 3 в процессе обязательно сведётся либо к 2 либо к 3. Дальше рассмотрим двоичную запись числа, очевидно, что ни одна операция не способна сократить число более, чем на один разряд. Число, заканчивающееся на 0, сокращается на разряд делением на 2. Рассмотрим число, оканчивающееся на n≥2 единиц. Прибавив 1 мы получим число, оканчивающееся на n нулей, т.е. за n+1 операцию уменьшим число на n разрядов. Очевидно, что за n операций уменьшить нечётное число на n разрядов невозможно, т.е. добавление 1 в этом случае гарантированно приводит к быстрейшему уменьшению. Число, оканчивающееся на 01 путём вычитания и деления на два два раза сокращается на 2 разряда, очевидно, что добавлением 1 быстрее уменьшить не получится, для этого достаточно рассмотреть 1(×n)01 +1 => 1(×(n+1))0 /2 => 1(×(n+1)) = 2+n+2 = n+4 операции, 1(×n)01 -1 /2 /2 => 1(×n) = 3+n+1=n+4 операции. Так что алгоритм в псевдокоде:

count = 0 
while n > 3
  case n mod 4
    0: n >> 2, count+=2
    1: n--, count++
    2: n >> 1, count++
    3: n++, count++
  end 
end
count+=n

в списке операций нет сравнения
есть.
процитируй

если оно четное

это по твоему что?
СРАВНЕНИЕ и ПРОВЕРКА НА ЧЕТНОСТЬ это одно и то же?
реквест был в «проверках»

Из этого неочевидно, глуп ли ты и/или толст и/или не умеешь читать,

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

а вот из этого, первый пункт таки проступает явно. Насчет минимального числа шагов не уверен, но как проверить на ноль в рамках условия без сравнения входного числа и результатов применения +,-,/ к нему, надеюсь, ты способен понять.

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

а вот из этого, первый пункт таки проступает явно. Насчет минимального числа шагов не уверен, но как проверить на ноль в рамках условия без сравнения входного числа и результатов применения +,-,/ к нему, надеюсь, ты способен понять.

я же глупый. Зачем говоришь загадками? Говори прямо.

А то мне непонятно: глупый я, или таки «способен понять»? Определись.

Это всё ты правильно написал, но я всё равно не вижу здесь профита:

1. на вход подаётся число X

2. к нему применяется твой алгоритм дающий N1 отложенных операций

3. выполняются N1 отложенных операций.

4. получается 0 на выходе

Почему вы считаете, что мой алгоритм, который СРАЗУ выполняется за N2 операций хуже? Да, у меня N2>=N1, но это «больше» очень ненамного, явно, что не вдвое, как у вас. Ибо вы для п2 выполняете как минимум N1 разрешённых операций, и ещё M запрещённых, потому у вас время итерации для каждого X равно N1+N1+M, что заведомо больше, чем моё N2.