Гость
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / [PHP, Perl, Python] Интересная задачка, нужен алгоритм / 20 сообщений из 20, страница 1 из 1
04.07.2018, 09:18
    #39669250
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Есть колода карт с числами, идеальный расклад 6 карт: 10,9,8,7,6,5
Брать можно только столько, сколько сбросили карт.
Предположим что выпало ,9,8,7,6,5,4 тогда надо сбросить 4 чтобы взять 10
Если выпало 10,9, ,7,6, ,4,3 тогда надо сбросить 4,3 чтобы взять 8,5
Усложняем, если выпало 10,9, ,7,6, , ,4 тогда надо сбросить 6,4 чтобы взять 8,5
Если выпало 10, ,8, ,6, , ,4 тогда надо сбросить 6,4 чтобы взять только 9,7

Путаюсь все время, помогите составить алгоритм.
язык не важен, какой удобнее PHP, Perl, Python
...
Рейтинг: 0 / 0
04.07.2018, 11:37
    #39669354
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Отсортировать набор (массив) и сбрасывать самые мелкие.
...
Рейтинг: 0 / 0
04.07.2018, 11:56
    #39669375
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
как бы понятно, но путает то что идеально должно быть 6 карт, но по факту в раздаче может прийти и 3 и 2 и 1
...
Рейтинг: 0 / 0
04.07.2018, 13:15
    #39669455
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Ну так сколько пришло в раздаче, столько мелких и сбрасывай.
...
Рейтинг: 0 / 0
04.07.2018, 13:23
    #39669461
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Нет, наверное вы не поняли.
Например в первом примере пришло 6 карт, а надо сбросить одну.
А в последнем примере, а сбросить надо 2, причем одна из них не мелкая.
...
Рейтинг: 0 / 0
04.07.2018, 14:06
    #39669495
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Получается примерно так:

[10,9,8,7,6,5,4,3,2,1] - это все возможные карты - 10 цифр в массиве
[0, 1, 1,0,0,1,1,1,1,0] - массив boolean, которые свидетельствуют, есть карта в изначальном твоем раскладе или нет (например для расклада [9,8,5,4,3,2])

Пробегаемся по массиву boolean - смотрим, что нам нужно - получаем [10,7,6] и 3 карты для сброса (все, что выше 5 и нет в изначальном раскладе).
Пробегаемся по массиву boolean в другую сторону (от нижших цифр к высшим) и сбрасываем 3 карты из имеющегося набора - сбрасываем [4,3,2].
...
Рейтинг: 0 / 0
04.07.2018, 14:07
    #39669496
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

И да, кто и как определяет, сколько пришло карт?
...
Рейтинг: 0 / 0
04.07.2018, 16:15
    #39669571
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Предположим что выпало ,9,8,7,6,5,4 тогда надо сбросить 4 чтобы взять 10
[011111 1000]

Если выпало 10,9, ,7,6, ,4,3 тогда надо сбросить 4,3 чтобы взять 8,5
[110110 1100]

Усложняем, если выпало 10,9, ,7,6, ,4 тогда надо сбросить 6,4 чтобы взять 8,5
[110110 1000] - тут нашел ошибку, глупо скидывать 6.
UPD. Усложняем, если выпало 10,9, ,7,6, ,4 тогда надо сбросить 4 чтобы взять 8

Если выпало 10, ,8, ,6, ,4 тогда надо сбросить 6,4 чтобы взять только 9,7
[101010 1000]

В последнем примере выше 4-х не хватает 3-х карт, но по факту нам надо скинуть только 2.
ВОТ как это вычислить?


ps. сколько пришло карт определяет случай =)
...
Рейтинг: 0 / 0
04.07.2018, 16:29
    #39669587
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Берем твой последний пример - первоначальный набор - 4 карты. Из первых 4 карт - 2 пропуска (в полном раскладе от 10 до 1). Т.е. нужно сбросить 2 карты.
...
Рейтинг: 0 / 0
04.07.2018, 16:34
    #39669591
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Т.е. ты знаешь сколько карт всего и сколько пропусков старших - число пропусков и есть сколько нужно скинуть.
Берем самый плохой случай:
[10 .. 1]
[0000001111] - [4,3,2,1] - начальный набор. Т.к. у тебя все старшие карты пропущены, по получается, что тебе нужно сбросить все карты.
...
Рейтинг: 0 / 0
04.07.2018, 16:36
    #39669594
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Опять же, условие не работает.
Если брать выше 4, то по вашей логике в последнем примере надо 3 карты, а не 2
Предположим что мы берем выше 4,перебираем вверх до булевой 1 и после считаем нули, тогда да, есть 2 нуля.

Но тогда мы не совпадаем со вторым примером:
Если выпало 10,9, ,7,6, ,4,3 тогда надо сбросить 4,3 чтобы взять 8,5
[110110 1100]
...
Рейтинг: 0 / 0
04.07.2018, 16:43
    #39669600
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnikОпять же, условие не работает.
Если брать выше 4, то по вашей логике в последнем примере надо 3 карты, а не 2
Предположим что мы берем выше 4,перебираем вверх до булевой 1 и после считаем нули, тогда да, есть 2 нуля.

Но тогда мы не совпадаем со вторым примером:
Если выпало 10,9, ,7,6, ,4,3 тогда надо сбросить 4,3 чтобы взять 8,5
[110110 1100]

1) Мы знаем сколько у нас карт всего (N = в примере 6).
2) Мы проходим по массиву от 10 до N (10 - самое первое значение) и проверяем, есть такая карта в наборе или нет. Если нет - увеличиваем счетчик пропусков.
3) Сбрасываем столько карт, сколько у нас получилось пропусков. Если число пропусков = N (все карты пропущены) - сбрасываем все карты.

Собственно все :)
...
Рейтинг: 0 / 0
04.07.2018, 17:18
    #39669620
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
да, похоже вы правы.
осталось запрограммировать как то.
...
Рейтинг: 0 / 0
04.07.2018, 17:54
    #39669629
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
 <?php
  $cardTotal=array(10,9,8,7,6,5,4,3,2,1);
  $cardOnHand=array(8,3,7,2);                 // что пришло на раздаче
  
  sort($cardOnHand);

  $cardMask=array();

  for ($i=0; $i<10; $i++)                         // ставим, что есть, чего нет
     {
         if ( in_array($i,$cardOnHand) ) $cardMask[]=1; 
         else $cardMask[]=0;
     }
  print_r($cardMask);
  print("<br>");

  $dropCount=0;
  for ($i=0; $i<count($cardOnHand); $i++)   // считаем пропуски
      {
          if ($cardMask[$i] == 0) 
                $dropCount++;                           // сколько нужно сбрсить
      }
  $cardForDrop=array_slice($cardOnHand,0,$dropCount);   // сбрасываем
  print_r($cardForDrop);
?>
...
Рейтинг: 0 / 0
04.07.2018, 17:56
    #39669632
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
yarnik,

Если $cardForDrop - пустой, то ничего не сбрасываем, у нас максимальная комбинация уже при раздаче.
...
Рейтинг: 0 / 0
04.07.2018, 18:48
    #39669659
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
$cardOnHand=array(10,9,7,6,4);
Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
 Array
(
    [0] => 0
    [1] => 0
    [2] => 0
    [3] => 0
    [4] => 1
    [5] => 0
    [6] => 1
    [7] => 1
    [8] => 0
    [9] => 1
)
<br>Array
(
    [0] => 4
    [1] => 6
    [2] => 7
    [3] => 9
)



=)
...
Рейтинг: 0 / 0
04.07.2018, 19:07
    #39669663
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
тоже самое на перле, и работает:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
@ideal_depo = (10,9,8,7,6,5);
@array_have = (10,9,7,6,4);

# Получаем общий массив
@hash{@ideal_depo,@array_have} = ();
@ideal_plus_have = sort { $b <=> $a } keys %hash;

# Создаем маску
for (@ideal_plus_have) {
	if ($_ ~~ @array_have) { push @cardMask, 1; }
	else { push @cardMask, 0; }
}

# Считаем нули
for (0 .. @array_have - 1) {
	if (!$cardMask[$_]) { $dropCount++; }
}

# Узнаем последние номера
@cardForDrop = splice(@array_have,-$dropCount);
print "cardForDrop: @cardForDrop\n";
# cardForDrop: 6 4
...
Рейтинг: 0 / 0
04.07.2018, 19:09
    #39669664
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Благодарю за помощь!
...
Рейтинг: 0 / 0
05.07.2018, 01:10
    #39669763
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Еще улучшил, теперь без маски
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
@ideal_depo = (10,9,8,7,6,5);
@array_have = (10,9,7,6,4);

# Создаем общий массив
@hash{@ideal_depo,@array_have} = ();
@ideal_plus_have = sort { $b <=> $a } keys %hash;

# Ходим по общему массиву и считаем сколько у нас карт нету, если счетчик больше чем имеем карт, выходим.
for (0 .. @ideal_plus_have) {
	last if ($_ + 1 > @array_have);
	unless ($ideal_plus_have[$_] ~~ @array_have) { $dropCount++; }
}

# Узнаем последние номера
@cardForDrop = splice(@array_have,-$dropCount);
print "cardForDrop: @cardForDrop\n";
# cardForDrop: 6 4
...
Рейтинг: 0 / 0
05.07.2018, 01:18
    #39669765
yarnik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP, Perl, Python] Интересная задачка, нужен алгоритм
Продолжаем улучшать =)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
@ideal_depo = (10,9,8,7,6,5);
@array_have = (10,9,7,6,4);

# Создаем общий массив
@hash{@ideal_depo,@array_have} = ();
@ideal_plus_have = sort { $b <=> $a } keys %hash;

# Проверяем в общем массиве первые карты на отсутствие по количеству имеющихся.
for (0 .. @array_have - 1) {
	unless ($ideal_plus_have[$_] ~~ @array_have) { $dropCount++; }
}

# Узнаем последние номера
@cardForDrop = splice(@array_have,-$dropCount);
print "cardForDrop: @cardForDrop\n";
# cardForDrop: 6 4
...
Рейтинг: 0 / 0
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / [PHP, Perl, Python] Интересная задачка, нужен алгоритм / 20 сообщений из 20, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]