LINUX.ORG.RU
Форум — Development  

счастливый билетик


0

0

В детстве любил пробивать билетики в троллейбусе :( Так как они были нумерованные, то на время поездки находил себе развлекуху - пытался с помощью четырех арифметических операций и всех цифр в номере билетика получить число 100. Знаки операций можно вставлять между любыми цифрами, но порядок следования цифр менять нельзя. Может у кого есть идеи по решению этой задачи программно?

anonymous
← Kylix 3 Enterprise
аналог doc++ для иерархии класов →

Есть такое умное название: "Генетическое программирование"(genetic programming).... Очень подходит для этой задачки. Подробности посмотри на google

anonymous
()

Перебором переберется для билетика из 6-ти цифр 1728*100000 вариантов. Наверно ты имел ввиду не генетическое программирование (которое нужно когда необходимо найти не оптимальный а близкий к оптимальному алгоритму) а динамическое программирование.

master ★
() 

не понял - откуда у перебора взялось такое число 1728*100000?
по идее должно быть 5^5? или нет?

перебором самый ништяк решать .. еще вопрос - можно ли расставлять скобки?

lg ★★
() 

вот кстати перебор на Pythone:

def mkstring(list):
    restr = ""
    for i in list:
        if str(i).isdigit():
            restr = restr + str(i);
        else:
            restr = restr + " " + str(i) + " "
    return restr

def mkexp(list, idx):
    global deep
    deep = deep + 1
    try:
        if eval(mkstring(list)) == 100:
            print list
            return list
    except ZeroDivisionError:
        return []
    if idx == len(list):
        return []
    else:
        ret = []
        for nl in range(idx + 1, len(list)):
            ret = mkexp(list[:nl]+["+"]+list[nl:], nl+1) + mkexp(list[:nl]+["-"]+list[nl:], nl + 1) + mkexp(list[:nl]+["*"]+list[nl:], nl + 1) + mkexp(list[:nl]+["/"]+list[nl:] , nl + 1)
        return ret

deep = 0
mkexp([3, 9, 6, 3, 7, 1], 0)
print deep

lg ★★
()

один знак между 6-ю цифрами (в троллейбусах по 6) 5-ю способами два знака 5*4 и т.д.

master ★
()

постой .. постой:
1 2 3 4 5 6
в каздую ячейку меожду иожно поставить "+" или "-" или "*" или "/" или ""
всего ячеек 5 - соответственно вариантов заплонения 5 ячеек 5^5
это все равно что найти вероятность выпадения последовательности 1, 3, 4, 5, 2
при кидании 5-ти гранного кубика на гранях которого написано 1, 2, 3, 4, 5.

lg ★★
() 

Исходная задача без скобок действительно решается тупым перебором.
Но если разрешить скобки, то вариантов перебора становится побольше...
А если еще и разрешить другие математические операции 
(чем возведение в степень хуже умножения?), 
то тогда задача становится просто неподъемной для перебора 
(особенно  на Pythone). 
С другой стороны, можно просто увеличить число циферок на номере.
5^(N-1) эта функция угробит любой суперкомпютер...

Именно поэтому я и вспомнил о genetic programming.
GP предназначено для создания алгоритмов с помощью 
генетического алгоритма (простите за тавтологию).
При этом скорость поиска у него значительно выше чем у перебора
и шансы отыскать не локальный а глобальный минимум очень высоки

anonymous
()

тебе master (*) (2002-09-04 13:23:24.192) по моему правильно заметил -- генетическое программирование здесь абсолютно не к месту -- здесь функция абсолютно weirdly себя ведет. А динамическим программированием как раз можно чего-то достичь за разумное время.

dilmah ★★★★★
()

я не догоняю где тут могут помочь генетические алгоритмы? какую целевую функцию ты можешь тут предложить которая подходит для данной задачи?

lg ★★
()

>какую целевую функцию ты можешь тут предложить которая подходит для данной задачи?

|100 -f(x)| где f(x) - результат работы очередного алгоритма

>А динамическим программированием как раз можно чего-то достичь за разумное время. http://onzi.narod.ru/chapter1.html: "Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач ?меньшего размера? и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размеров - от меньших к большим. Преимущество динамического программирования заключается в том, что раз уж какая-то подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново [Шень 95, п. 8.1; Ахо 79, п. 2.8]."

То есть, как я понял, имеется ввиду классическое "разделяй и властвуй". Мне правда не приходит в голову, каким образом можно эффективно определить в данном случае эти самые подзадачи, но это конечно не означает, что это сделать нельзя. Просто это не тривиально. (кстати, если есть идея, как это сделать - поделитесь, было бы очень познавательно) Но если получится, то это будет наилучшим решением.

GP в этом отношенни проще. Задал целевую функцию, нашел подходящее представление алгоритма в виде кода и функцию вычисляющую по коду результат работы алгоритма. Далее нужны две примитивные операции на коде: мутация и скрещевание(crossower) Ну и конечно селекция, выкидывающая слабых. Практически все части GA стандартны и неплохо описанны. Запускай и жди результата.

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

anonymous
()

|100 - f(x)| - :)
решая эту задачу таким образом для последовательномти допустим 346371 - ты не найдешь ни одного решения - а оно есть! Сдесь то задача состоит в том что надо найти такое состояние которое дает ровно 100 а не ~100(101 или 99 или 98)

ga в данном случае полностью сосет .. как впрочем всё кроме перебора :)

lg ★★
()

2lg

>ga в данном случае полностью сосет .. как впрочем всё кроме перебора :)

обоснуй, отче ;-)

доказать это строго теоретически, невозможно. А практически ga на сегодня самый проверенный метод поиска решения(~2 миллиарда лет использования ;-). Конечно в скорости он значительно уступает другим (например методу градиентного спуска), но по способности отыскивать глобальный минимум в мерзких задачах за приемлемое время ему нет равных.

Так что твое утверждение, что ga не сможет отыскать оптимум среди 3125 вариантов по меньшей мере очень сомнительно.

anonymous
()

с 5^5 комбинациями ты наверное погорячился, где-то (2^20)-1. Эта беда на прологе должна быстро писатся

babai ★
()

>Эта беда на прологе должна быстро писатся Еще бы она также быстро считалась, как и пишется... :(

>(2^20)-1.

Э... о чем это?

anonymous
()

множество из двадцати элементов (по 5 каждого) - общее число
подможеств = 2^|Set| минус пустое множество. Можно проделать чистку конечно из-за коммутативности операций.
Ну пролог не для быстроты конечно, а для простоту нужен ;)

babai ★
() 

ребята ну хорош гнать то - вот вам апгрейднутая версия на pythonе
находит ВСЕ(в предыдущий по одному в каждом ответвлении) варианты .. считает сколько всего вариантов:
=============cut&paste=============
#!/usr/bin/env python
import sys

def usage():
    print "usage: ./bil.py <number>"
    sys.exit(0);

def mkexp(sbil, idx):
    global prev
    global deep
    global glist
    deep = deep + 1
    try:
        if eval(sbil) == 100:
            glist.append(sbil)
    except ZeroDivisionError:
        return []
    if idx == len(sbil):
        return []
    else:
        ret = []
        for nl in range(idx + 1, len(sbil)):
            ret = mkexp(sbil[:nl]+"+"+sbil[nl:], nl+1) + \
                  mkexp(sbil[:nl]+"-"+sbil[nl:], nl + 1) + \
                  mkexp(sbil[:nl]+"*"+sbil[nl:], nl + 1) + \
                  mkexp(sbil[:nl]+"/"+sbil[nl:] , nl + 1)
        return ret

av = sys.argv
ac = len(av)

if (ac < 2):
   usage();

deep = 0
glist = []
prev = 0
mkexp(av[1], 0)
for i in glist:
    print "%d: %s" %(glist.index(i), i)

print "deep: %d" %deep
====================cut&paste==============================

Я занимаюсь нейросетями и экспертными системами уже 2 года - одна из реализаций есть с применением ген алгоритмов
поэтому как специалист по нейросетям :) я вам говорю что тут это дело всасывает по полной.
Вы наверное просто услышали что вот есть такая вот хрень - вроде клевая и можно юзать.
Но на самом деле даже и не знаете что это такое ..

Напомню что ген алгоритмы, нечеткая логика, градиенты - они предназначены для решения
задач в более менее нормальный промежуток времени но при этом не гарантируют
точность решения. А нам нужно быть 100 пудово быть увереными что мы получим 100 а не что то близкое к 100.
> но по способности отыскивать глобальный минимум в мерзких задачах за приемлемое время ему нет равных.
В том то и дело что у нас тут нет экстримальной задачи (есть конечно но не в данном контексте): вот посмотри на графики распределения глубна/значение
439872: http://lgarc.narod.ru/pics/bil/439872.png
234894: http://lgarc.narod.ru/pics/bil/234894.png
895134: http://lgarc.narod.ru/pics/bil/895134.png
110 и -110 это точки где значения > 110 или < -110

соответственно |100 - f(x)| будет вести себя подобным образом .. и чтоб получить правильный
ответ с применением ген алгоритмов тебе придеться только молиться на тервер чтоб
случайно не выкинулся НУЖНЫЙ для решения элемент который с точки зрения га находиться
за гранью .. и его не выкидывают только из за того что ему 'везет' :)

lg ★★
() 

К сожалению, коллега, мне приходится признать, что Вы в данном вопросе правы.

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

Так что для того, чтобы решать данную задачу для более-менее длинных билетиков
необходима программа, работающая с большей скоростью (или более мощный компьютер).
Вот мой вариант на с++. Я буду рад услышать коментарии по поводу данной реализации.
По моим тестам она в 10 раз быстрее Python'овской реализации (без оптимизации при компиляции)
 
ps. Кстати, число 5^5 надо бы заменить на 2*5^5, поскольку необходимо учитывать 
унарный минус перед первой цифрой.

----------------------------------------------------------------------
// The program search all ways to get a some value using only a tickets digits and arithmetical operations.
//
// Copyright: Witali Kusnezow  mail: witali.kusnezow@neuroinformatik.ruhr-uni-bochum.de
//
// This program is free software, covered by the GNU General Public License,
// and you are welcome to change it and/or distribute copies of it under GPL conditions

#include <iostream>
#include <vector> 
#include <map> 
#include <hash_map> 
#include <sstream> 

enum Operation
{
  Minus,Plus,Divide,Multiply,Concatinate
};

typedef vector<Operation> Operations;
typedef vector<double>    Digits;

ostream& operator<< (ostream& streamA, Operation operA)
{
  switch (operA)
    {
    case Plus: 		streamA<<"+"; break;
    case Minus: 	streamA<<"-"; break;
    case Multiply:	streamA<<"*"; break;
    case Divide:	streamA<<"/"; break;
    default: ;
    };//switch 
  return streamA;
};

void print( const Digits& numbersA, Operations & operationsA) 
{
  Digits::const_iterator it2L= numbersA.begin();
  Operations::const_iterator itL = operationsA.begin();
  for (; itL!= operationsA.end(); cout<< *it2L++<<*itL++);
  cout<< *numbersA.rbegin() <<endl;
};

template <class Predicate>
bool calcOp( Digits & numbersA, Operations & operationsA, Predicate predA)
{
  Operations::iterator top, opIterL = top = operationsA.begin();
  Digits::iterator digIterL;
  for(;;)
    {
      opIterL = find_if( opIterL, operationsA.end (),  predA);

      if (opIterL == operationsA.end()) break;

      digIterL= numbersA.begin() + (opIterL - top);
      double & newValueL = *digIterL++;
      double & argValueL = *digIterL;
      switch (*opIterL)
	{
	case Plus: 	newValueL += argValueL; break;
	case Minus: 	newValueL -= argValueL; break;
	case Multiply:	newValueL *= argValueL; break;
	case Divide:
	  {
	    newValueL /= argValueL; break;
	  }
	case Concatinate: (newValueL *= 10)  += argValueL; break;
	default: cerr<<"Error"<<endl; break;
	};//switch 
      numbersA.erase(digIterL);
      operationsA.erase(opIterL);
      if ( operationsA.empty()) return true;
    }
  return operationsA.empty();
};

double calculate( Digits numbersA, Operations operationsA )
{
  if ( 1 != (numbersA.size() - operationsA.size()))
    {
      cerr<<"Illegal arguments in calculate"<<endl;
      return 0;
    }
  
  if ( calcOp( numbersA, operationsA,  bind2nd(equal_to<Operation>(), Concatinate)) ||
       calcOp( numbersA, operationsA,  bind2nd(greater_equal<Operation>(), Divide)) ||
       calcOp( numbersA, operationsA,  bind2nd(greater_equal<Operation>(), Minus)) )
    return numbersA[0];

  cerr<<"Error in calculate()"<<endl;
  return 0;
};

void inc( Operations& opA )
{
  for ( Operations::reverse_iterator iterL= opA.rbegin(); iterL != opA.rend(); ++iterL)
    {
      if (*iterL == Concatinate)
	*iterL = Minus;
      else
	{
	  *iterL = Operation( *iterL +1);
	  return;
	}
    }
};

void testAll(const  Digits& numbersA)
{
  Digits numbers2A( numbersA);
  numbers2A[0] = -numbersA[0];

  hash_map< int, int> counterL;
  double tmpResL;
  int    intResL;
  Operations opL(numbersA.size()-1,Minus);
  const Operations opEndL(numbersA.size()-1,Concatinate);
  for(; opL!=opEndL; inc(opL))
    {
      tmpResL= calculate( numbersA, opL);
      if ( tmpResL == int(tmpResL)) ++counterL[tmpResL];

      tmpResL= calculate( numbers2A, opL);
      if ( tmpResL == int(tmpResL)) ++counterL[tmpResL];
    }
  map< int, int> sortedCounterL( counterL.begin(), counterL.end());
  cout<<"N\t| found"<<endl;
  for( map< int, int>::iterator countIterL= sortedCounterL.begin(); countIterL != sortedCounterL.end(); ++countIterL)
    cout<< countIterL->first<<"\t"<<countIterL->second<<e
ndl;
};

void findAll(const Digits& numbersA, int aimA)
{
  Digits numbers2A( numbersA);
  numbers2A[0] = -numbersA[0];
  Operations opL(numbersA.size()-1,Minus);
  const Operations opEndL(numbersA.size()-1,Concatinate);
  for(; opL!=opEndL; inc(opL))
    {
      if (aimA == calculate( numbersA, opL) )  print(numbersA,  opL);
      if (aimA == calculate( numbers2A, opL) ) print(numbers2A, opL);
    }
};

int main (int argc, char * argv[])
{
  if ( (argc!=2) && (argc!=3) )
    {
      cerr<<"The program search all ways to get the value using only a tickets digits and arithmetical operations."<<endl<<endl
	  <<"Copyright: Witali Kusnezow (witali.kusnezow@neuroinformatik.ruhr-uni-bochum.de)"<<endl<<en
dl
	  <<"This program is free software, covered by the GNU General Public License,"<<endl
	  <<"  and you are welcome to change it and/or distribute copies of it under GPL conditions "<<endl<<endl
	  <<"Usage:"<<endl<<"\t"<<argv[0]<&
lt;" ticket [value]"<<endl;
      return -1;
    }

  Digits digitsL;
  {
    istringstream  streamL( argv[1]);
    std::transform (istream_iterator<char >(streamL),
		    istream_iterator< char >(),
		    std::back_inserter(digitsL),
		    bind2nd(minus<double>(),48)); 
  }
  if ((*min_element(digitsL.begin (), digitsL.end ())<0) &&
      (*max_element (digitsL.begin (), digitsL.end ())>9) )
    {
      cerr<< "The first argument must be positive integer number"<<endl;
      return -1;
    };
  if (argc==2)
    testAll(digitsL);
  else
    {
      istringstream  streamL( argv[2]);
      int aimL;
      streamL >> aimL;
      findAll( digitsL, aimL);
    }
  return 0;
}; //main

anonymous
()

Минус нельзя ставить перед первой цифрой - иначе нарушается условие задачи в котором сказанно что можно ставить знак _между_ любыми цифрами. прогу несмог закомпилировать (нет c++ компилятора) но на вид вроде все нормально.

lg ★★
() 

2dilmah

thanks

2lg 
>нет c++ компилятора

это легко исправить, лови ссылочку
http://gcc.gnu.org/install/binaries.html

2all
строки программы в которых встречается \t
таинственным образом испортились при пресылке:
<&
lt;
следует читать <<
a
<<e
ndl;
как <<endl;

anonymous
() 

Да забыл:
>Минус нельзя ставить перед первой цифрой ...

Тогда надо убрать строчки:
в testAll():
      tmpResL= calculate( numbers2A, opL);
      if ( tmpResL == int(tmpResL)) ++counterL[tmpResL];

в findAll():
     if (aimA == calculate( numbers2A, opL) ) print(numbers2A, opL);

anonymous
()

> http://gcc.gnu.org/install/binaries.html
нет у меня места для этого монстра :( .. ненавижу ставить бинари .. и там нет бинарей подходящих для меня ..

lg ★★
()

Немного запаздал к началу дискусии. Вопросик а как вы подсчитывали число возможных комбинаций арифметических операторов (ну и операции cat).

anonymous
()

у меня это было deep - то есть сколько будет глубина рекурсии - столько операторов мы и подставили ..

lg ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Kylix 3 Enterprise
Development
аналог doc++ для иерархии класов →