Беседка - русскоязычный форум в Израиле: Задачка для программеров 2 - Беседка - русскоязычный форум в Израиле

Перейти к содержимому

Внимание! Правила игр находятся на первой странице каждой игры!

  • 2 Страниц +
  • 1
  • 2
  • Вы не можете создать новую тему
  • Тема закрыта

Задачка для программеров 2

#1 Пользователь офлайн   Элличка 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 265
  • Регистрация: 18 Октябрь 07
  • Город:Israel

Отправлено 20 Октябрь 2007 - 19:44

опишите самый быстрый способ проверки числа явлеется ли оно 2^Х? то есть какая-то степень двух.
Если мужчина долго-долго смотрит тебе в глаза, можешь быть уверена: всё остальное он уже осмотрел.
0

#2 Пользователь офлайн   michaelD 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 791
  • Регистрация: 26 Сентябрь 06

Отправлено 24 Декабрь 2007 - 13:01

Просмотр сообщенияЭлличка (20.10.2007, 16:44) писал:

опишите самый быстрый способ проверки числа явлеется ли оно 2^Х? то есть какая-то степень двух.



не знаю............, но есть другая классная задачка !!!!
0

#3 Пользователь офлайн   Н@талья 

  • Термоядерная смесь ретроградства и вольнодумства
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 76 838
  • Регистрация: 11 Февраль 04
  • Пол:Женский
  • Город:Кирьят Ата
  • Интересы:Мутировать людей

Отправлено 24 Декабрь 2007 - 13:38

:)
Никто никому ничего не должен © Я.
0

#4 Пользователь офлайн   Саш_а 

  • Участник
  • PipPip
  • Группа: Участник
  • Сообщений: 12
  • Регистрация: 03 Ноябрь 15
  • Пол:Женский
  • Город:Спб
  • Интересы:Кино, игры, казино

Отправлено 25 Февраль 2016 - 15:41

Нет на этом форуме программеров :rudolph:
Мои игры ;-)
0

#5 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 25 Февраль 2016 - 21:53

Просмотр сообщенияЭлличка (20 Октябрь 2007 - 19:44) писал:

опишите самый быстрый способ проверки числа явлеется ли оно 2^Х? то есть какая-то степень двух.

Перевести в двоичную систему. Если получится единица с нулями - условие выполнено.
0

#6 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 25 Февраль 2016 - 21:53

Просмотр сообщенияЭлличка (20 Октябрь 2007 - 19:44) писал:

опишите самый быстрый способ проверки числа явлеется ли оно 2^Х? то есть какая-то степень двух.

Перевести в двоичную систему. Если получится единица с нулями - условие выполнено.
0

#7 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 25 Февраль 2016 - 21:53

Просмотр сообщенияЭлличка (20 Октябрь 2007 - 19:44) писал:

опишите самый быстрый способ проверки числа явлеется ли оно 2^Х? то есть какая-то степень двух.

Перевести в двоичную систему. Если получится единица с нулями - условие выполнено.
0

#8 Пользователь офлайн   Вомич 

  • я это...
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 9 971
  • Регистрация: 13 Февраль 04
  • Пол:Мужской
  • Город:Тутошний я

Отправлено 27 Февраль 2016 - 23:06

Просмотр сообщенияMrFatCat (25 Февраль 2016 - 21:53) писал:

Перевести в двоичную систему. Если получится единица с нулями - условие выполнено.

Я правильно понимаю что программированием вы никогда не занимались?
Чтобы с умом потратить деньги, нужно всего лишь две вещи. Сами догадайтесь, какие...
0

#9 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 27 Февраль 2016 - 23:21

Не правильно.
0

#10 Пользователь офлайн   Вомич 

  • я это...
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 9 971
  • Регистрация: 13 Февраль 04
  • Пол:Мужской
  • Город:Тутошний я

Отправлено 28 Февраль 2016 - 10:37

Просмотр сообщенияMrFatCat (27 Февраль 2016 - 23:21) писал:

Не правильно.

тогда я задам еще вопрос.
в числе 256 сколько итераций понадобится чтобы понять что это действительно степень двойки? а в числе 1028?
Чтобы с умом потратить деньги, нужно всего лишь две вещи. Сами догадайтесь, какие...
0

#11 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 28 Февраль 2016 - 11:15

Просмотр сообщенияВомич (28 Февраль 2016 - 10:37) писал:

в числе 256 сколько итераций понадобится чтобы понять что это действительно степень двойки? а в числе 1028?

7 и 11 соответственно.
Но в условии не сказано о среде программирования. Если компьютер работает в двоичной системе (как большинство современных компьютеров), введенное число хранится в памяти уже в двоичном формате. В этом случае потребуется 0 итераций, перевод в двоичную систему уже осуществлен при вводе.
Кстати, при вводе с клавиатуры числа 1028 произойдет не 11 итераций, а больше, потому что будут вводиться последовательно цифры 1, 10, 102 и 1028. То есть, 1+4+7+11=23 итерации.
0

#12 Пользователь офлайн   Вомич 

  • я это...
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 9 971
  • Регистрация: 13 Февраль 04
  • Пол:Мужской
  • Город:Тутошний я

Отправлено 28 Февраль 2016 - 11:26

Просмотр сообщенияMrFatCat (28 Февраль 2016 - 11:15) писал:

7 и 11 соответственно.
Но в условии не сказано о среде программирования. Если компьютер работает в двоичной системе (как большинство современных компьютеров), введенное число хранится в памяти уже в двоичном формате. В этом случае потребуется 0 итераций, перевод в двоичную систему уже осуществлен при вводе.
Кстати, при вводе с клавиатуры числа 1028 произойдет не 11 итераций, а больше, потому что будут вводиться последовательно цифры 1, 10, 102 и 1028. То есть, 1+4+7+11=23 итерации.

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

#13 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 28 Февраль 2016 - 12:38

Просмотр сообщенияВомич (28 Февраль 2016 - 11:26) писал:

В условии требуется предложить самый быстрый способ.

Что может быть быстрее извлечения уже имеющейся информации?

Аналогичную задачу недавно решал практически: разработать самый быстрый алгоритм поиска слова в тексте.
Маленькая деталь: на php.
Самым быстрым окзалось: разбить текст на массив букв, а искомое слово на второй массив букв, и цикл в цикле.
Потому что особенность среды php: текст хранится уже в виде массива букв, мы сразу запускаем циклы, без медленного побуквенного перебора.
На тексте в несколько десятков мегабайт и подстроке несколько сот килобайт регулярка съедала десятки секунд времени и пол-гига памяти; "цикл в цикле" меньше секунды и несколько десятков мегабайт памяти.
0

#14 Пользователь офлайн   nindzja 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 225
  • Регистрация: 06 Август 09

Отправлено 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 итераций;
0

#15 Пользователь офлайн   Вомич 

  • я это...
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 9 971
  • Регистрация: 13 Февраль 04
  • Пол:Мужской
  • Город:Тутошний я

Отправлено 22 Март 2016 - 17:54

Просмотр сообщенияnindzja (22 Март 2016 - 17:23) писал:

Получилось около 8 итераций;

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

#16 Пользователь офлайн   Вомич 

  • я это...
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 9 971
  • Регистрация: 13 Февраль 04
  • Пол:Мужской
  • Город:Тутошний я

Отправлено 22 Март 2016 - 17:55

Просмотр сообщенияMrFatCat (28 Февраль 2016 - 12:38) писал:

Что может быть быстрее извлечения уже имеющейся информации?

а где вы держите уже имеюшуюся информацию?
Чтобы с умом потратить деньги, нужно всего лишь две вещи. Сами догадайтесь, какие...
0

#17 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 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 секунд
?>

0

#18 Пользователь офлайн   Вомич 

  • я это...
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 9 971
  • Регистрация: 13 Февраль 04
  • Пол:Мужской
  • Город:Тутошний я

Отправлено 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 секунд
?>


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

#19 Пользователь офлайн   MrFatCat 

  • חשב את עצמו
  • PipPipPipPip
  • Группа: Модераторы
  • Сообщений: 3 868
  • Регистрация: 27 Апрель 13
  • Пол:Мужской
  • Город:נצרת עילית

Отправлено 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;
}

0

#20 Пользователь офлайн   nindzja 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 225
  • Регистрация: 06 Август 09

Отправлено 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 раза быстрее
Аналогично можно ещё ускорять и ускорять.
0

  • 2 Страниц +
  • 1
  • 2
  • Вы не можете создать новую тему
  • Тема закрыта

1 человек читают эту тему
0 пользователей, 1 гостей, 0 скрытых пользователей


Внешний вид