Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Задача по информатике про индейцев

 PHP.SU

 Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (2): [1] 2 »   

> Описание: помогите
Поиск в теме | Версия для печати
Oditor
Отправлено: 13 Ноября, 2010 - 10:27:28
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
Вообщем мне задали задачу про индейцев, смысл следующий (язык - РНР)

Индейцы двигаются в линию друг за другом и их высоты описывает массив (обычный массив 0...n, где значениями являются высоты индейцев - целые позитивные числа)

Пример

<-------направление движения
array(182, 190, 178, 174, 181, 170, 161, 186);

Каждый индеец видит перед собой:

всех кто его ниже
+ 1 индеец (назовём его индеец Х) кто выше или равен ему по росту
+ начиная с индеца Х тех кто за ним идёт и выше его

На какой по счёту позиции в этом ряду находится индеец, который видит больше всего человек? Если их несколько - достаточно только одного.

например в данной шеренге:
175 210 169 200 183 176 163 179 232 160 142
0 1 2 3 4 5 6 7 8 9 10

больше всех (8 человек видит восьмой индеец),
последний видит двух и седьмой видит четверых




Главный вопрос состоит в том, как сделать данный алгоритм как можно быстрее? (у нас будут проведены тесты, кто быстрее тот получит дополнительные пункты)
 
 Top
Dekker8
Отправлено: 13 Ноября, 2010 - 10:40:50
Post Id



Частый гость


Покинул форум
Сообщений всего: 139
Дата рег-ции: Янв. 2009  


Помог: 0 раз(а)
я так понял нужно найти самое большое число в массиве?
 
 Top
SAD Модератор
Отправлено: 13 Ноября, 2010 - 11:23:18
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2508
Дата рег-ции: Май 2009  
Откуда: Днепропетровск, Украина


Помог: 75 раз(а)
Так играйте по честному)) Додумайтесь сами
 
 Top
Oditor
Отправлено: 13 Ноября, 2010 - 11:54:19
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
SAD пишет:
Так играйте по честному)) Додумайтесь сами


кто сказал что другие играют по честному?))




П.С. нет, максимум в массиве находить не надо...пример:

240, 164, 175

он покажет тебе что максимум у первого но он никого же не видит вообще
 
 Top
DlTA
Отправлено: 13 Ноября, 2010 - 13:12:14
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)
Oditor пишет:
Главный вопрос состоит в том, как сделать данный алгоритм как можно быстрее?
всмысле быстро решить задачу или короткий код?
 
 Top
Oditor
Отправлено: 13 Ноября, 2010 - 13:14:52
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
не быстро решить и не короткий код, а чтобы выполнялся быстро (например при тестирование берут список из 300 индейцев и функции участников, чья функция быстрее ответ даст тот и выйграл)
 
 Top
DlTA
Отправлено: 13 Ноября, 2010 - 13:17:13
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)
вообще задача решается просто
создаете еще один массив который будет длинной с первый
и циклом с двойной вложенностью проходите по первому
тоесть первый поочередно задает номер проверяемого индейца
а во втором проверяете сколько перед ним меньшего роста
если есть ниже то инкрементируете соответствующую позицию во втором массиве
если нет, так нет.
и потом определить где у Вас самое большое число во втором массиве
 
 Top
Oditor
Отправлено: 13 Ноября, 2010 - 13:19:27
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
DlTA пишет:
вообще задача решается просто


решается то просто, только предложенный Вами вариант не является достаточно быстрым.

(Отредактировано автором: 13 Ноября, 2010 - 13:19:53)

 
 Top
DlTA
Отправлено: 13 Ноября, 2010 - 13:30:40
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010  


Помог: 53 раз(а)
тогда можно во внутреннем цикле проходить
не с начала
а от имеющегося положения по направлению в начало
и заканчивать проход встретив первого кто ниже
имеющееся значение во тором массиве сохранять проверяемому увеличив на 1

варианты закончились
 
 Top
Вездеход
Отправлено: 13 Ноября, 2010 - 13:35:14
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 820
Дата рег-ции: Апр. 2008  
Откуда: Россия


Помог: 0 раз(а)
это простая задача. попробуйте нарисовать себе эту задачу и сами додумаетесь до решения...

как вариант (если уж сами не можете) могу такой вариант предложить:
PHP:
скопировать код в буфер обмена
  1.  
  2. <?PHP
  3. echo '<pre>';
  4.  
  5. /**
  6.         * author woo
  7.         * version 1.0
  8. **/
  9.         $indeyci = array(182, 190, 178, 174, 181, 170, 161, 186);
  10.         $kachestvo = true; // false если нужно видеть всех кто ниже
  11.         $napravlenie = 'left'; // or right
  12.         $result = array();
  13.         /*------------------------------*/
  14.        
  15.         if($napravlenie=='left') $indeyci = array_reverse($indeyci);
  16.         $temp = $indeyci;
  17.         foreach($indeyci as $n=>$i) {
  18.                 $result[$n] = 0;
  19.                 unset($temp[$n]);
  20.                 foreach($temp as $t_n=>$t_i) {
  21.                         if($kachestvo) {
  22.                                 if($t_i>=$i) break;
  23.                                 else $result[$n]++;
  24.                         }
  25.                         else {
  26.                                 if($t_i<$i) $result[$n]++;
  27.                         }
  28.                 }
  29.         }
  30.         foreach($indeyci as $n=>$ind) {
  31.                 echo "индеец №".($n+1)." с ростом ".$ind." видит впереди ".$result[$n]." человек<br>";
  32.         }
  33. ?>
  34.  


входных параметров только 3:
$indeyci - массив с ростом индейцев
$kachestvo - качество (true/false), если true - видет только тех кто стоит перед ним и ниже его. если false - видит всех кто ниже его ростом и стоит перед ним
$napravlenie - направление движения - left/right
(Добавление)
мой вариант кода на локальном компе отработал оч быстро...
я взял массив из 10000 индейцев случайным образом,
в среднем время работы скрипта - 0.22 - 0.24 секунды


-----
о великий nl2br!
Хочешь невероятных ощущений? Юзай блокнот! Блокнот - чудеса сбываются!
Чем меньше вы знаете PHP - тем ценнее мои знания!
 
 Top
Oditor
Отправлено: 13 Ноября, 2010 - 14:23:57
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
к сожалению вышеописанный скрипт не является правильным....В нём не учитывается, что при массиве

200 183 176 163 175

индеец с ростом 175 будет видеть всех остальных индейцев

Цитата:

+ 1 индеец (назовём его индеец Х) кто выше или равен ему по росту
+ начиная с индеца Х тех кто за ним идёт и выше его


имеется ввиду следующее:

175 210 169 200 183 176 163 179 232 160 142

седьмой индеец (ростом 163) видит шестого, пятого, четвёртого (но не видит второго, так как между вторым и четвёртым стоит третий, которого он не видит)
 
 Top
Вездеход
Отправлено: 13 Ноября, 2010 - 14:28:00
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 820
Дата рег-ции: Апр. 2008  
Откуда: Россия


Помог: 0 раз(а)
Oditor
вы сами то поняли что написали?
Цитата:
В нём не учитывается, что при массиве 200 183 176 163 175
индеец с ростом 175 будет видеть всех остальных индейцев

т.е. вы утверждаете что 175 больше 200?
или у вас какая то особая математическая система?
(Добавление)
так.. секундочку
я думал мы идем в таком виде:
(показываю на звездочках - 1 человек, 1 строка)
1 *****
2 ***
3 ******
4 *******
5 ****
6 *****
7 ******
8 ***
я делал в коде проверку на рост в меньшую сторону. т.е. тот кто выше - видет тех кто ниже. вам я так понял надо наоборот? т.е. 2й видет 3его и 4го... (в моем примере)
ну это не проблема. просто меняйте мой код - отличие будет только в знак больше(>) \ меньше(<)


-----
о великий nl2br!
Хочешь невероятных ощущений? Юзай блокнот! Блокнот - чудеса сбываются!
Чем меньше вы знаете PHP - тем ценнее мои знания!
 
 Top
Oditor
Отправлено: 13 Ноября, 2010 - 14:41:40
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
Спойлер (Отобразить)




создайте простой хтмл файл с данным содержанием и поймёте условия задачи






Добавил: а по вашему примеру победителем является либо первый либо четвёртый индеец, оба видят троих людей.

(Отредактировано автором: 13 Ноября, 2010 - 14:43:09)

 
 Top
Варяг
Отправлено: 13 Ноября, 2010 - 15:14:50
Post Id



Новичок


Покинул форум
Сообщений всего: 61
Дата рег-ции: Окт. 2010  


Помог: 0 раз(а)
вот набросок, просто стало интересно Радость
Можно его дописать, пока не учитывает если увидит такого же индейца. идет все задом наперед (чисто по-русски)
PHP:
скопировать код в буфер обмена
  1.  
  2.             $indeici=array(175,210,169,200,183,250,163,179,232,240,142);
  3.  
  4.              $end=end($indeici);
  5.              $dal=0;
  6.              for($i=count($indeici);$i>=0;$i--){
  7.                  echo $i,'<br>';
  8.                  $x=prev($indeici);
  9.  
  10.                   if ($end>$x){
  11.                         $dal++;
  12.                         } else {
  13.                         $end=$x;$dal=0; }
  14.  
  15.                   if ($i==0){
  16.                         echo 'самый зоркий индеец',$end,'он видит аж ',$dal-2,'индейцев';
  17.                   }
  18.              }
  19.  
  20.  

(Отредактировано автором: 13 Ноября, 2010 - 15:21:43)

 
 Top
Oditor
Отправлено: 13 Ноября, 2010 - 16:17:10
Post Id


Новичок


Покинул форум
Сообщений всего: 10
Дата рег-ции: Нояб. 2010  


Помог: 0 раз(а)
Вариант Варяга

$indeici=array(200,183,176,163,175);

Самый зоркий индеец 200 он видит аж 0 индейцев



хотя самым зорким является индеец с ростом 175 - он видит аж 4 индейца.
 
 Top
Поиск в теме | Версия для печати
Страниц (2): [1] 2 »
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Напишите за меня, пожалуйста »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
  



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB