minds2web
 
 [Most Recent Entries] [Calendar View] [Friends]

Below are the 2 most recent journal entries recorded in artemvoroztsov's LiveJournal:

    Friday, June 1st, 2007
    3:03 am
    Уроки Ruby. Как с помощью рубина получить волшебные кубики?

    На одной из олимпиад по программированию была следующая простая задача на перебор (см. ниже). И был приведен авторский код на языке C++ (см. ниже). Я посмотрел на все это и понял, что нужно немедленно переписать все на Ruby (см. еще ниже).  

    ( Read more... )

     

    •  

    Задача "Волшебные игральные кубики"

    Стандартный игральный кубик имеет 6 граней, на которых написаны числа {1,2,3,4,5,6}. Давайте рассмотрим нестандартные кубики, на гранях которых могут быть поставлены различные числа с возможными повторениями. Представьте себе, что у меня есть 3 таких кубика. Я предлагаю своему партнеру выбрать любой из этих кубиков, который ему больше понравился, а сам беру себе другой кубик из двух оставшихся. Далее мы начинаем играть: каждый бросает свой кубик, и выигрывает тот, на чьем кубике выпадет большее число. Оказывается, что при большом числе бросаний в среднем я буду в выигрыше, то есть я буду чаще выигрывать у партнера. Даже если партнер поменяет кубик, например, возьмет кубик, которым играл я, то он все равно будет проигрывать, если я воспользуюсь правом выбрать себе кубик из двух оставшихся. Может ли такое быть? Оказывается, может. Весь секрет в числах, которые расставлены на гранях кубиков. Пусть на гранях трех кубиков числа расставлены так:

    • первый кубик 1, 1, 4, 4, 7, 7,
    • второй кубик - 2, 2, 5, 5, 5, 5,
    • третий кубик - 3, 3, 3, 3, 6, 6.

    Нетрудно проверить, что второй кубик будет выигрывать у первого в среднем в пяти случаях из девяти, а проигрывать только в 4-х случаях из 9. Третий кубик будет выигрывать у второго также в 5 случаях из 9. А первый будет выигрывать у третьего также в 5 случаях из 9. (Правильнее сказать: в 20 случаях из 36, так как количество вариантов выпадения граней двух кубиков равно 6 6. Но это то же самое, так как дроби можно сокращать.)

    Сформулируем сказанное в других терминах. Кубики можно сравнивать друг с другом: кубик A "сильнее" кубика B, если в среднем на кубике A выпадает число большее, чем число, которое выпадает на кубике B. На практике сравнить кубики несложно - нужно просто много раз кинуть два кубика одновременно и считать сколько раз A выиграл B, B выиграл A, и сколько раз была ничья. Но умелый программист может написать функцию test(A,B), которая абсолютно точно выдаст какой из кубиков "сильнее". Удивительный факт заключается в том, что бывают тройки кубиков A, B, C в которых A сильнее B, B сильнее C, и C сильнее A, то есть, говоря математическим языком, отношение "сильнее" не транзитивно и ориентированном графе, представляющем это отношение, есть циклы длины 3.

    Ваша задача заключается в том, чтобы, используя наименьшее количество различных чисел, найти их расстановку (конечно, с повторениями) на гранях трех кубиков такую, чтобы кубики обладали описанным выше "волшебным" свойством.

     

     

    Решение на C++ (автор неизвестен)

    #include <iostream>
using namespace std;
const int  Q = 6,  // число граней игрального кубика
          Mmax = 1000; 
int N;     // число найденных решений
int  P,    // число возможных цифр
     M;    // число игральных кубиков — число
           //  наборов размера Q из P элементов
           //  с возможными повторениями.  
int  C[Mmax][Q],       // коллекция кубиков.
     E[Q] ;

int test(int i, int j) {   // сравнение двух кубиков C[i] и C[j]
   int k, l, t = 0;
   for (k = 0; k < Q; k++)  
       for (l = 0; l < Q; l++)
           if (C[i][k] > C[j][l]) 
               t++;
           else 
               if (C[i][k] < C[j][l]) t--;
   if (t > 0) return 1; 
   else if (t < 0) return -1;
   else return 0;
}

int main(){
   int j, k, q, t;

   M = 0;
   N = 0;
   cout << "Введите число цифр P=";
   cin  >> P; // P = 4;
   // Построение множества всех кубиков
   for (q = 0; q < Q; q++) 
       C[0][q] = E[q] = 1;
   for (M = 1; M < Mmax; M++) {
       for (q = Q - 1; q >= 0; q--) {
           if (E[q] < P) {
               int s;
               E[q]++;
               for (s = q + 1; s < Q; s++)
                   E[s] = E[q];
               break;
           }
       }
       if (q < 0) break;
       for (q = 0; q < Q; q++) 
           C[M][q] = E[q];
    }

    if (M > Mmax)
       cout << "Только " << Mmax << " кубиков будут рассматриваться.\n";

    for (E[0] = 0; E[0] < M - 2; E[0]++) { // Перебор решений
       for (E[1] = E[0] + 1; E[1] < M - 1; E[1]++) {
           t = test(E[0], E[1]);
           if (t != 0) {
               for (E[2]=E[1]+1; E[2]<M; E[2]++) {
                   if (t == test(E[1],E[2]) && t == test(E[2],E[0]) ) {
                       for (j = 0; j < 3; j++) {
                           // Вывод решения
                           cout << "(";
                           for (q = 0; q < Q; q++) { 
                               if (q) cout << ",";
                               cout << C[E[j]][q];
                           }
                           cout << ")";
                           if (t == 1)  cout << ">";
                           if (t == -1) cout << "<";
                           cout << endl;
                       }
                       cout << endl;
                       N++;
                   }
               }
           }
       }
   }
   cout << "M N: " << M << ' ' << N << endl;
   return 0;
}

     

     

    Решение на Ruby.

    Это задача решается методом перебора. По сути, нам нужно перебрать различные сочетания элементов из промежутка (1..P) с возможными повторениями, и для получившегося множества сочетаний перебрать всевозможные тройки (уже без повторения). Естественно для этого написать методы для экземпляров класса Array - массивов.

     

    class Array
   # перебрать все наборы с возможными повторениями
   def tuples (size, &block)
       tuples0(size,[],0,block)
   end
       
   private
   # перебрать все наборы элементов с возможными 
   # повторениями, при условии, что уже набран
   # частично набор ary, и в него нужно добрать 
   # элементы из хвоста массива self[i..].
   def tuples0(size,ary,i,block)
       if ary.size == size
           # получен очередной набор
           # отдадим его ассоциированному блоку
           block[ary] 
       elsif i < self.size
           # возьмем self[i]
           ary.push self[i]
           tuples0(size,ary,i,block)
           ary.pop

           # или пропустим self[i]
           tuples0(size,ary,i+1,block) 
       end
   end
end

# сгенерируем сочетания 3-х элементов из 5 
# с возможными повторениями 
(1..5).to_a.tuples(3) do |tuple|
   puts tuple.inspect
end

     

    Вывод программы:

    [1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 3]
[1, 3, 4]
[1, 3, 5]
[1, 4, 4]
[1, 4, 5]
[1, 5, 5]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 2, 5]
[2, 3, 3]
[2, 3, 4]
[2, 3, 5]
[2, 4, 4]
[2, 4, 5]
[2, 5, 5]
[3, 3, 3]
[3, 3, 4]
[3, 3, 5]
[3, 4, 4]
[3, 4, 5]
[3, 5, 5]
[4, 4, 4]
[4, 4, 5]
[4, 5, 5]
[5, 5, 5]

     

    Предъявленный метод tuples у экземпляров класса Array генерирует различные сочетания с возможными повторениями из элементов массива. Этот метод вызывается как метод конкретного массива, который внутри определений имеет имя self (сам объект). Алгоритм генерации основан на методе рекурсии. Введем в задачу дополнительные параметры - ary и i:

    Подзадача: Пусть у нас уже взято несколько элементов, и они собраны в массиве ary. Необходимо доложить в этот набор элементы так, чтобы он имел размер size, используя при этом только элементы хвоста массива: self[i], self[i+1], …

    Эту подзадачу решает функция tuples0(size,ary,i,block), при этом эта подзадача легко сводится сама к себе, и её можно решить, используя рекурсию.

    Задача. Загрузите и установите Ruby (http://www.ruby-lang.org/en/downloads). Используя редактор SciTe?, который поставляется вместе с дистрибутивом, наберите данный текст программы и запустите её, нажав на F5. Создайте новые функции subsets и subsets0, которые генерирую наборы без повторений элементов. Для этого нужно взять за основу функции tuples и tuples0, а именно, сначала нужно точно повторить их (скопировать), заменить везде tuples на subsets, а также заменить строку

    tuples0(size,ary,i,block)

    на строку

    subsets0(size,ary,i+1,block)

     

    Решите эту задачу, не поленитесь. Проверить работу можно с помощью строки

     

    (1..5).to_a.subsets(3) { |subset|  puts subset.inspect }

    Эта строка должна вывести 10 различных сочетаний 3 элементов из 5 первых натуральных чисел. без повторений

    Для решения задачи о волшебных тройках осталось сделать совсем немного - определить метод сравнения двух наборов. Для этого давайте переопределим оператор <=> так, чтобы он возвращал -1, 0 или 1, в зависимости от того, какой из двух наборов чисел выигрывает:

    • 1 - первый выигрывает;
    • 0 - ничья;
    • -1 - второй выигрывает.

    Этот оператор именно таким образом определен для обыкновенных чисел. Вот определение этого метода сравнения двух наборов ("абстрактных игральных кубиков"):

     

    class Array
   def <=>(ary)
       res = 0
       self.each do |x|
           ary.each do |y|
               res += (x<=>y)
           end
       end
   end
end

    Заметьте, что в Ruby можно свободно "дописывать" существующие классы, добавляя в них новые методы и переопределяя существующие.

    Функции subsets и tuples слишком сильно повторяют друг друга. Это не соответствует основной концепции Ruby - не повторяйся (принцип DRY - don't' repeat yourself). Этих повторений можно избежать, введя дополнительный аргумент у функции tuples0. Кроме того, хотелось бы, чтобы функции tuples и subsets, если их вызывать без ассоциированного блока, просто возвращали массив наборов. Это сделано в приведённом ниже полном коде программы.

    Решение задачи выглядит следующим образом:

     

    class Array
   def <=>(ary)
       res = 0
       self.each do |x|
           ary.each do |y|
               res += (x<=>y)
           end
       end
       res <=> 0
   end
   
   # пояснение этой функции нам придётся отложить
   # до лучших времён
   def set_optional_block(block)
       if block.nil?
           [result=[], lambda {|x| result << x }]
       else
           [nil, block]
       end
   end
       
   # перебрать все наборы с возможными повторениями
   def tuples(size, &block)
       result,block = set_optional_block(block)
       tuples0(size,[],0,0,block)
       result
   end
   
   # перебрать все наборы без повторений
   def subsets(size, &block)
       result,block = set_optional_block(block)
       tuples0(size,[],0,1,block)
       result
   end
       
   private
   # перебрать все наборы элементов при условии, что уже 
   # набрана часть набора ary и нужно добрать элементов 
   # из хвоста массива self[i..].
   # Повторения возможны, если norepeat = 0.
   def tuples0(size,ary,i,norepeat,block)
       if ary.size == size
           block[ary.dup] 
       elsif i < self.size
           # возьмем self[i]
           ary.push self[i]
           tuples0(size,ary,i+norepeat,norepeat,block)
           ary.pop

           # или пропустим self[i]
           tuples0(size,ary,i+1,norepeat,block)
       end
   end

end

puts "Волшебные тройки:"
puts (1..4).to_a.tuples(6).subsets(3).select { |t|
   ((t[0]<=>t[1]) + (t[1]<=>t[2]) + (t[2]<=>t[0])).abs == 3
}.inspect

    Данный код не намного короче кода на языке С++. Но заметьте, что приведённое здесь решения содержит определение функции tuples и subsets, которые могут быть использованы при решении многих других алгоритмических задач. Причём эти функции можно использовать с ассоциированным блоком или без, в зависимости от того, хоти те вы проитерировать наборы ("пробежаться" по ним), или хотите получить массив наборов. Задача была разбита на отдельные методы, так что само решение по сути, состоит из 4-х последних строчек кода.

    Данный код можно существенно ускорить, если сделать кэширование значений сравнения:

        def <=>(ary)
       @cache = Hash.new if @cache.nil?
       return @cache[ary] if @cache.has_key?(ary)
       res = 0
       self.each do |x|
           ary.each do |y|
               res += (x<=>y)
           end
       end
       @cache[ary]=(res <=> 0)
   end

    Это кэширование позволяет уменьшить время поиска с 11,3 сек. до 2,7 сек. (на ноутбуке Pentium M, 1.7MHz). Для получения информации об использовании памяти и процессорного времени удобно использовать модуль benchmark:

     

    require 'benchmark'
puts Benchmark.measure {
   puts [1,2,3,4].to_a.tuples(6).subsets(3).select { |t|
       ((t[0]<=>t[1]) + (t[1]<=>t[2]) + (t[2]<=>t[0])).abs == 3
   }.size
}

    Данный код напечатает число найденных волшебных троек (43, досадно, что не 42) и время, потраченное на вычисления: процессорное время, потраченное на пользовательский код, процессорное время, потраченное на выполнение системных вызовов и реальное время, которое прошло, пока вычислялся заданный блок.

    Документацию по различным классам и их методам можно получить, используя графическое приложение fxri, включенное в дистрибутив Ruby под Windows.

     

    См. также

    • http://ru.wikibooks.org/wiki/Ruby - книжка про Ruby на русском языке.
    • http://acm.mipt.ru/bin/view/Ruby - учебные материалы на сайте МФТИ.
    • Programming Ruby, Dave Thomas with Chad Fowler and Andy Hunt (Программирование на Ruby, Дейв Томас, совместно с Чадом Фоулером и Энди Хантом)
    • Agile Web Development with Rails - Pragmatic Programmers Guide, Dave Thomas (Гибкое программирование под Web на Rails, Дейв Томас)


    Current Mood: creative
    Current Music: Transoceanic
    Wednesday, May 30th, 2007
    11:50 pm
    Уроки Ruby. Быстрая сортировка.

    См. теорию на Algorithms.QuickSort

    Конечно на практике нужно пользоваться методами sort и sort!, определенными для всех стандартных контейнеров. Эти функции возвращают массив.

    В учебных целях реализуем алгоритм быстрой сортировки на самом Ruby.

     

    Метод 1

    Попробуем использовать метод partition, определенный для экземпляров Enumerable:

     

    class Array 
       def qsort
          return self.dup if size <=1
          e = self.first # делить будем по первому элементу
          l,r = partition   {|x| x <= e}
          a,l = l.partition {|x| x == e}
          l.qsort + a + r.qsort # конкатенация трех массивов
       end
    end

     

    Метод 2

    Но удобно делить исходный массив сразу на три массива. Для этого определим метод partition3:

     

    class Array 
       # given block should return 0,1 or 2
       # -1 stands for 2
       # outputs three arrays
       def partition3
          a = Array.new(3) {|i| []}
          each do |x|
             a[yield(x)].push x
          end
          a
       end
       def qsort
          return self.dup if size <=1
          a,l,r = partition3 {|x| first <=> x}
          l.qsort + a +  r.qsort
       end
    end

    Можно сделать более универсальную функцию partitionN

     

    class Array
       def partitionN
          inject(Hash.new) { |f,x|
             key = yield(x)
             f[key]=[] unless f.has_key?(key)
             f[key].push x
             f
          }.to_a.sort.map{|pair| pair[1]}
       end
    end
    p [0,1,2,3,5,4,3,6,7,5,4,3,4,65,7,87,4523].partitionN {|x| x % 4}
    #
    # => [[0, 4, 4, 4], [1, 5, 5, 65], [2, 6], [3, 3, 7, 3, 7, 87, 4523]]
    #

     

     

    Реализация qsort!

    Необходима также версия функции сортировки, которая сортирует массив "на месте". Вот она:

     

    class Array
       def qsort!
          self.replace(self.qsort)
       end
    end
    a = [1,7,6,5,4,3,2,1]
    a.qsort!
    p a
    #
    # => [1, 1, 2, 3, 4, 5, 6, 7]
    #

     

    Метод, создающий методы-модификаторы

    Целый ряд методов в стандартных классах Ruby имеет аналоги, модифицирующие сам объект. Имена этих функций заканчиваются на !, например, sort!, uniq!, map!.

    Их все можно было определить разом. Например так:

     

    def make_modifiers(*methods)
       methods.each do |method|
          eval " 
             class #{self.to_s}
                def #{method}!(*args,&block)
                   self.replace(self.#{method}(*args,&block))
                end
             end
              "
       end
    end
    class Array
       make_modifiers :sort, :uniq, :map
    end

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



    Current Mood: creative
    Current Music: Naomi
About LiveJournal.com

Advertisement