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

[нубство] задачка


0

1

Привет, ЛОР. Такую вот задачку дал знакомый: есть цифры 1, 3, 4, 6. Можно использовать операторы +, -, *, /, унарный минус, скобки. «Склеивать» (13+46) цифры нельзя. Надо получить 24, используя все цифры по одному разу. Всё происходит в 10-чной системе счисления. После неудачи при попытке решить в уме написал программу. К сожалению, я не программист, поэтому написал «как умею»: 

my @nums = (1, 3, 4, 6, -1, -3, -4, -6);

#numbers
foreach my $n1 (@nums){
	foreach my $n2 (@nums){
		next if abs($n2) == abs($n1);
		foreach my $n3 (@nums){
			next if abs($n3) == abs($n2) || abs($n3) == abs($n1);
			foreach my $n4 (@nums){
				next if abs($n4) == abs($n1) || abs($n4) == abs($n2) || abs($n4) == abs($n3);

				#operators
				foreach my $o1 (' + ', ' - ', ' * ', ' / '){
					foreach my $o2 (' + ', ' - ', ' * ', ' / '){
						foreach my $o3 (' + ', ' - ', ' * ', ' / '){							
								
							#brackets
							foreach my $i (0..63){
								
								my %br = ();
								foreach my $j (0..5){
									($br{$j.'o'}, $br{$j.'c'}) = ($i & 1 << $j) ? ('(', ')') : ('', '');
								}
					

								my $str = $br{'0o'}.$br{'1o'}.$br{'2o'}.$n1.$o1.$br{'3o'}.$br{'4o'}.$n2.$br{'0c'}.$o2.$br{'5o'}. $n3.$br{'4c'}.$br{'1c'}.$o3.$n4.$br{'2c'}.$br{'3c'}.$br{'5c'};								
								
								print "\n$str => ".eval($str);								
							}							
						}
					}
				}
			}
		}		
	}
}
Да, она просто перебирает все варианты. Потом grep-ом можно достать подходящий. Правда, кажется, несколько вариантов упущено, а несколько лишних добавлено. Собственно, пара вопросов: в каком виде лучше всего хранить данные для таких задач? Да, в perl есть eval и можно просто собрать строку, но eval есть не везде. Какие вообще алгоритмы и идеи тут надо использовать?



Последнее исправление: m_ (всего исправлений: 2)
← Страуструп про ЛИСП
функция XSetWindowBorder →

Я помню эту задачу, я также помню, что не нашел решения для нее.

rival ★★
()

> есть цифры 1, 3, 4, 6. Можно использовать операторы +, -, *, /, унарный минус, скобки

(--3 - 1) * 4 * 6
Используются: скобки, унарный минус, минус, умножение.

Slavaz ★★★★★
()
Ответ на: комментарий от rival

> Читерство.
Почему? :)
по условию задачи разрешено. Не указано ведь какой унарный минус - постфиксный или префиксный... ;)

Slavaz ★★★★★
()
Ответ на: комментарий от Slavaz

Потому, что −−3 = −(−3) = 3 ≠ 2?
Но мне все равно нравится твое решение =)

rival ★★
()
Ответ на: комментарий от FractaIL

Знаю и так, протормозил просто что-то.

m_
() автор топика
Ответ на: комментарий от anonymous7

Спасибо большое, примерно это я и искал, посмотрю.

m_
() автор топика

Какие вообще алгоритмы и идеи тут надо использовать?

Здравый смысл.

У тебя есть набор из N чисел. Ты можешь от туда вынуть любые два числа, применить к ним какую-нибудь бинарную операцию и положить обратно результат. В итоге у тебя получится набор из N-1 чисел. Унарный минус кол-во элементов не уменьшает, но с ним много наборов не сделаешь.

Дальше сам.

ival ★★
()
Ответ на: комментарий от rival

Ясно =)
Не разглядел юмора просто, так как — - это не унарный минус же.

UVV ★★★★★
()

Что-то у тебя очнеь сложно получилось.


use strict;
use warnings;

my @nums = ( 1, 3, 4, 6 );
my @used = ();
my @ops  = ( '+', '-', '*', '/' );
my @result;
my $npos  = 0;
my $max   = 0;
my $brack = 0;

sub get_num {
    my $k = $_[0];
    my $i;

    for ( $i = $k ; $i < @nums ; $i++ ) {
        return $i if !$used[$i];
    }

    return undef;
}

sub iter {
    my $i;
    $max++;

    for ( $i = 0 ; $i < @nums ; $i++ ) {
        my $t = get_num($i);
        $i = $t;

        last unless defined $t;

        $used[$t] = 1;

        foreach my $c ( $nums[$t], -$nums[$t] ) {
            push @result, $c;

            if ( $max < 4 ) {
                foreach (@ops) {
                    push @result, $_;
                    iter();
                    pop @result;
                }
            }
            else {
                  br_iter(0,\@result);
            }

            pop @result;
        }

        $used[$t] = 0;
    }

    $max--;
}

sub br_iter
{
  my ($n, $ref)=@_;
  my $i;
  
  for ($i=$n; $i < scalar @{$ref}; $i++) {
     if ( $brack < 2 && ($i % 2 == 0)) {
       my $tmp=$ref->[$i];
       
       if ($brack==0 && $i < (scalar @$ref -1)) {
         $brack=1;
         $ref->[$i]="(".$tmp;
         br_iter($i+1, $ref);
         
         $brack=0;
         $ref->[$i]=$tmp;
       }
       elsif ($brack == 1) {
         $brack=2;
         $ref->[$i]=$tmp.")";
         br_iter($i+1, $ref);
         
         $brack=1;
         $ref->[$i]=$tmp;
         return if ($i == (scalar @$ref)-1);
       }
     }
  }
  
  my $str=join(" ", @$ref);
  my $rc=eval ( $str );
  
  if ( !$@ &&  $rc==24) {
    print  "$str\n";
  }
}

iter();
OxiD ★★★★
()
Ответ на: комментарий от OxiD

;))

Без eval тоже можно - в польскую запись и через стек выполнить выражение.

OxiD ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Страуструп про ЛИСП
Development
функция XSetWindowBorder →