КИТА unofficial

Ваши интересы => Викторины и конкурсы => Тема начата: vimmax от Февраль 15, 2007, 10:45:44



Название: "Искусство программирования" (задача 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
     mov ax, 0
     mov cx, 16
m: rcl bx, 1
     adc ax, 0
     loop m
в результате в ax кол-во единиц. но что-то мне подсказыавет, что это не самый лучший вариат....


Название: 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
    {
        static BitCounter()
        {
            hash.Add(0, 0);
            hash.Add(1, 1);
            hash.Add(2, 1);
            hash.Add(3, 2);
            ...
            hash.Add(65535, 16);
            hash.Add("0", 0);
            hash.Add("1", 1);
            hash.Add("2", 1);
            hash.Add("3", 2);
            ...
            hash.Add("65535", 16);
        }

        static Hashtable hash = new Hashtable();

        public static int Count(object x)
        {
            if (hash.Contains(x)) return (int) hash[x];
            return 0;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Кол-во единиц: {0:D}", BitCounter.Count(3));
            Console.WriteLine("Кол-во единиц: {0:D}", BitCounter.Count("3"));
            Console.ReadLine();
        }
    }

Кстати насчет абсурдности идеи как таковой, индексы в СУБД MS SQL Server предназначены для ускорения поиска и представляют собой ничто иное как сбалансированные деревья.


Название: Re: "Искусство программирования" (задача 3)
Отправлено: mars от Февраль 27, 2007, 12:56:33
Ставишь мультиплексоры, а после них счетчики:). Работать будет быстрее всего остального.
Очень хотелось бы схемку с мультиплексором увидеть ....
хе-хе