Название: "Искусство программирования" (задача 3) Отправлено: vimmax от Февраль 15, 2007, 10:45:44 Написать подпрограмму, вычисляющую количество единиц в бинарном представлении целого числа, например в числе 6 две единицы (6 = 0110bin), в числе 7 три единицы (7 = 0111bin).
Условия: Реализацию этого алгоритма можно предложить на любом языке программирования. Мой ответ на ANSI С. Будет защитан только самый быстрый алгоритм, т.е. подпрограмма должна быть оптимизирована по времени. Название: Re: "Искусство программирования" (задача 3) Отправлено: BODROV от Февраль 15, 2007, 03:14:31 Цитировать mov bx, x в результате в ax кол-во единиц. но что-то мне подсказыавет, что это не самый лучший вариат....mov ax, 0 mov cx, 16 m: rcl bx, 1 adc ax, 0 loop m Название: Re: "Искусство программирования" (задача 3) Отправлено: vimmax от Февраль 15, 2007, 04:12:13 BODROV - Ответ #1 - вау, скока программистов на асме нашлось!!!!
Ответ хороший, но не самый быстрый. Фишка данной задачи в том, что ответ можно реализовать на любом языке программирования. Хотя ответ немного абсурдный.....но самый быстрый. Название: Re: "Искусство программирования" (задача 3) Отправлено: Archangel от Февраль 16, 2007, 11:59:01 Ставишь мультиплексоры, а после них счетчики:). Работать будет быстрее всего остального.
Название: Re: "Искусство программирования" (задача 3) Отправлено: vimmax от Февраль 16, 2007, 01:42:07 Archangel - Ответ #3 - Может быть и быстрее, но сейчас тема "Искусство программирования", а не "Искусство схемотехники" )))
Название: Re: "Искусство программирования" (задача 3) Отправлено: vimmax от Февраль 16, 2007, 05:10:44 Такс,....ну что товарисчи ?? Даже никто и не пытается? В общем даю подсказку:
Оптимизация программ обычно ведется в одном из двух направлений: 1.оптимизация по скорости с увеличением занимаемой памяти 2.оптимизация по занимаемой памяти в ущерб скорости. В данной задаче время выполнения алгоритма уменьшается за увеличения занимаемой памяти... Название: Re: "Искусство программирования" (задача 3) Отправлено: BODROV от Февраль 16, 2007, 05:27:29 создать массив скажем из 65535 элементов, где заведомо указать в i-том элементе количество единиц числа i :rofl:
Название: Re: "Искусство программирования" (задача 3) Отправлено: Sochin от Февраль 16, 2007, 05:37:00 создать массив скажем из 65535 элементов, где заведомо указать в i-том элементе количество единиц числа i :rofl: А для оптимизации по времени поиска элемента использовать хеш-таблицу или двоичное дерево. :rofl:Название: Re: "Искусство программирования" (задача 3) Отправлено: vimmax от Февраль 16, 2007, 05:46:51 BODROV, Sochin - Все бы хорошо, но приведите пример кода, можно без компиляции и без лишних элементов. Хоть пару строк....
Название: Re: "Искусство программирования" (задача 3) Отправлено: BODROV от Февраль 16, 2007, 06:00:09 Цитировать const ;)a: array [0..65535] of integer = (0,1,1,2,1,2,2,3,1,2 ...и так далее... 16); var z: word; begin readln(z); writeln('код-во единиц: ', a[z]); end. Название: Re: "Искусство программирования" (задача 3) Отправлено: vimmax от Февраль 16, 2007, 06:07:00 BODROV - Ответ#9 - Правильный ответ, самый быстрый. Скорость в ущерб памяти :) +1.
Sochin - Ответ #7 - интересно было-бы посмотреть реализацию с хеш-таблицами и бинарным деревом. Название: Re: "Искусство программирования" (задача 3) Отправлено: BODROV от Февраль 16, 2007, 06:11:30 BODROV - Ответ#9 - Правильный ответ, самый быстрый. Скорость в ущерб памяти :) +1. :rofl:супер!!! в ущерб не только памяти, но психичекого состояния программера... я б после заполнения матрицы а точно двинулся бы :D вообже такой вариант еще вчера появлялся, но я его отбросил, как ответ абсурдней абсурдного ::) Название: Re: "Искусство программирования" (задача 3) Отправлено: Sochin от Февраль 17, 2007, 03:58:40 Sochin - Ответ #7 - интересно было-бы посмотреть реализацию с хеш-таблицами и бинарным деревом. Вот так с помощью хэша можно искать для целых или скажем для строк(C#): Код: public class BitCounter Кстати насчет абсурдности идеи как таковой, индексы в СУБД MS SQL Server предназначены для ускорения поиска и представляют собой ничто иное как сбалансированные деревья. Название: Re: "Искусство программирования" (задача 3) Отправлено: mars от Февраль 27, 2007, 12:56:33 Ставишь мультиплексоры, а после них счетчики:). Работать будет быстрее всего остального. Очень хотелось бы схемку с мультиплексором увидеть ....хе-хе |