Мелкие задачки для крупных мозгов 14

The Svin

Совершенно с Вами согласен (по поводу Дундука)

ну вот.... как что - сразу обижатся.

Чем вам не угодило программирование на Asmе?

Ну разве так можно?



Никто ваши тексты не заменял. Просто немного сдвинули систему отсчёта.



И потом завтра вы и не заметите что тут что-то было.



С первым апреля Вас )) Улыбнитесь

 

Не самое оптимальное решение, сложность N*log(N). Требует 8 проходов по исходным данным и возможность делать realloc для результирующего массива. Какие у кого идеи по поводу оптимизации будут?

Код (Text):

1. <?php
2.  
3. function find(&$b,$s,$e,$v)
4. {
5.   if($s==$e)
6.     return $s;
7.   $m=intval(($s+$e)/2);
8.   if($b[1+2*$m]>=$v)
9.     return find($b,$s,$m,$v);
10.   else
11.     return find($b,$m+1,$e,$v);
12. }
13.  
14. function calc1(&$a,&$b,$s)
15. {
16. //для каждого слова массива A ищем в массиве B ключ, учитывая только биты 31..(S+5)
17. //и делаем пометку в соседнем слове, что нужно добавить ключ у которого первые биты V[31..S]
18.   foreach($a as $v)
19.   {
20.     $i=find($b,0,$b[0],$v);
21.     $b[1+$i*2+1]|=1<<(($v>>$s)&31);
22.   }
23.   $o=$b[0];
24. //Вычисляем новую длину массива статистики
25.   $n=0;
26.   for($i=0;$i<$o;$i++)
27.   {
28.     for($j=0;$j<32;$j++)
29.       $n+=($b[1+2*$i+1]>>$j)&1;
30.   }
31.   $k=$n;
32. //А здесь расширяем массив B, записывая в него удлинённые на 5 бит ключи
33.   for($i=$o;--$i>=0;)
34.   {
35.     for($j=32;--$j>=0;)
36.     if($b[1+2*$i+1]&(1<<$j))
37.     {
38.       --$k;
39.       $b[1+2*$k]=($b[1+2*$i]&-(1<<($s+5)))|($j<<$s)|((1<<$s)-1);
40.       $b[1+2*$k+1]=0;
41.     }
42.   }
43.   $b[0]=$n;
44. }
45.  
46. function calc(&$a)
47. {
48.   $b=Array(1,0xFFFFFFFF,0);
49.   calc1($a,$b,30);
50.   calc1($a,$b,25);
51.   calc1($a,$b,20);
52.   calc1($a,$b,15);
53.   calc1($a,$b,10);
54.   calc1($a,$b,5);
55.   calc1($a,$b,0);
56.   foreach($a as $v)
57.     ++$b[1+2*find($b,0,$b[0],$v)+1];
58.   return $b;
59. }
60.  
61. $a=Array();
62. for($i=0;$i<0x10;$i++)
63.   $a[$i]=rand(0,0xF)<<28;
64.  
65. $b=calc($a);
66.  
67. foreach($a as $v)
68.   echo("$v<br>");
69. echo("<br>");
70. for($i=0;$i<$b[0];$i++)
71.   echo("{$b[1+2*$i]} {$b[1+2*$i+1]}<br>");
72.  
73. ?>