Задачка для программеров 2
#1
Отправлено 20 Октябрь 2007 - 19:44
#8
Отправлено 27 Февраль 2016 - 23:06
MrFatCat (25 Февраль 2016 - 21:53) писал:
Я правильно понимаю что программированием вы никогда не занимались?
#10
Отправлено 28 Февраль 2016 - 10:37
MrFatCat (27 Февраль 2016 - 23:21) писал:
тогда я задам еще вопрос.
в числе 256 сколько итераций понадобится чтобы понять что это действительно степень двойки? а в числе 1028?
#11
Отправлено 28 Февраль 2016 - 11:15
Вомич (28 Февраль 2016 - 10:37) писал:
7 и 11 соответственно.
Но в условии не сказано о среде программирования. Если компьютер работает в двоичной системе (как большинство современных компьютеров), введенное число хранится в памяти уже в двоичном формате. В этом случае потребуется 0 итераций, перевод в двоичную систему уже осуществлен при вводе.
Кстати, при вводе с клавиатуры числа 1028 произойдет не 11 итераций, а больше, потому что будут вводиться последовательно цифры 1, 10, 102 и 1028. То есть, 1+4+7+11=23 итерации.
#12
Отправлено 28 Февраль 2016 - 11:26
MrFatCat (28 Февраль 2016 - 11:15) писал:
Но в условии не сказано о среде программирования. Если компьютер работает в двоичной системе (как большинство современных компьютеров), введенное число хранится в памяти уже в двоичном формате. В этом случае потребуется 0 итераций, перевод в двоичную систему уже осуществлен при вводе.
Кстати, при вводе с клавиатуры числа 1028 произойдет не 11 итераций, а больше, потому что будут вводиться последовательно цифры 1, 10, 102 и 1028. То есть, 1+4+7+11=23 итерации.
В условии требуется предложить самый быстрый способ.
Для любого числа.
Проверка каждого бита, таким способом не является.
#13
Отправлено 28 Февраль 2016 - 12:38
Вомич (28 Февраль 2016 - 11:26) писал:
Что может быть быстрее извлечения уже имеющейся информации?
Аналогичную задачу недавно решал практически: разработать самый быстрый алгоритм поиска слова в тексте.
Маленькая деталь: на php.
Самым быстрым окзалось: разбить текст на массив букв, а искомое слово на второй массив букв, и цикл в цикле.
Потому что особенность среды php: текст хранится уже в виде массива букв, мы сразу запускаем циклы, без медленного побуквенного перебора.
На тексте в несколько десятков мегабайт и подстроке несколько сот килобайт регулярка съедала десятки секунд времени и пол-гига памяти; "цикл в цикле" меньше секунды и несколько десятков мегабайт памяти.
#14
Отправлено 22 Март 2016 - 17:23
х=256;
а=1; ...... х > а? Да; // 256 > 1
а=а * 2; х > а? Да; // 256 > 2
а=а * 2; х > а? Да; // 256 > 4
а=а * 2; х > а? Да; // 256 > 8
а=а * 2; х > а? Да; // 256 > 16
а=а * 2; х > а? Да; // 256 > 32
а=а * 2; х > а? Да; // 256 > 64
а=а * 2; х > а? Да; // 256 > 128
а=а * 2; х > а? Нет; // 256 не > 256
........... х = а?; Да; // 256 = 256
Получилось около 8 итераций;
#15
Отправлено 22 Март 2016 - 17:54
nindzja (22 Март 2016 - 17:23) писал:
это уже предлагалось.
нужно быстрее.
и можно использовать математические действия и побитовые операции.
#16
Отправлено 22 Март 2016 - 17:55
MrFatCat (28 Февраль 2016 - 12:38) писал:
а где вы держите уже имеюшуюся информацию?
#17
Отправлено 22 Март 2016 - 18:22
<?php $starttime = time(); for($i=0;$i<100000000;$i++)$t = $i; $time = time() - $starttime; echo $time; // В среднем 20 секунды $starttime = time(); for($i=0;$i<100000000;$i++)$t = decbin($i); $time = time() - $starttime; echo $time; // В среднем 50 секунд ?>
#18
Отправлено 22 Март 2016 - 18:40
MrFatCat (22 Март 2016 - 18:22) писал:
<?php $starttime = time(); for($i=0;$i<100000000;$i++)$t = $i; $time = time() - $starttime; echo $time; // В среднем 20 секунды $starttime = time(); for($i=0;$i<100000000;$i++)$t = decbin($i); $time = time() - $starttime; echo $time; // В среднем 50 секунд ?>
понятно что вызов функции добавляет к времени пробега программы. тем более что непонятно чего вы хотите добиться переводя число из десятичного в двоичного.
и совсем непонятно как из этой функции вы поймете является ли она степенью двойки.
#19
Отправлено 23 Март 2016 - 11:15
Вомич (22 Март 2016 - 18:40) писал:
Я доказываю, что перевод десятичного в двоичное - это не просто 1 операция, а операция с микроскопическими затратами ресурсов.
В первом цикле 1 действие: присвоение значения переменной.
Во втором цикле 2 действия: перевод числа из десятичного в двоичный формат и присвоение переменной двоичного значения.
Код демонстрирует, что время выполнения обеих операций примерно равное.
Вомич (22 Март 2016 - 18:40) писал:
На php весьма просто:
function chk($i) { $t = decbin($i); // 1 - перевод двоичный формат $t .= ""; // 2 - смена типа переменной $t = str_teplace("0", "",$t); // 3 - удаление в строке нулей if($t == "1")return TRUE; // 4 - вывод результата return FALSE; }Я специально разделил первые 3 действия для наглядности. На самом деле это тоже имеет значение, и раза в 2 быстрее будет работать:
function chk($i) { $i = str_teplace("0", "", "".decbin($i)); if($i == "1")return TRUE; return FALSE; }
#20
Отправлено 23 Март 2016 - 13:16
А пока ускорим 1-й способ.
х=255;
а=1; ...... х > а? Да; // 255 > 1
а=а * 4; х > а? Да; // 255 > 4
а=а * 4; х > а? Да; // 255 > 16
а=а * 4; х > а? Да; // 255 > 64
а=а * 4; х > а? Нет; // 255 не > 256
а=а / 2; х = а? Нет; // 255 не = 128
........................... //ответ: 255 не является степенью 2
Получилось около 4 итераций, то есть в 2 раза быстрее
Аналогично можно ещё ускорять и ускорять.