Генерация кодов серого — n-битные коды серого
Вопрос задан hackerrank, и я получил решение, но в последних тестовых случаях есть проблема в решении.
Вопрос ниже.
1 <= $n <= 65
Ниже приведена 1-битная последовательность (n = 1)
0 1
Выход
1
Ниже приводится 2-битная последовательность (n = 2)
00 01 11 10
Выход
11 10
Ниже приводится 3-битная последовательность (n = 3)
000 001 011 010 110 111 101 100
Выход
111 101 100
Ниже приводится 4-битная последовательность (n = 4)
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111
1110 1010 1011 1001 1000
Выход
1010 1011 1001 1000
Пример решения
Ниже приведены шаги для генерации 3-битного списка кодов Грея из списка 2-битных списков кодов Грея.
- L1 = {00, 01, 11, 10} (список 2-битных кодов серого)
- L2 = {10, 11, 01, 00} (обратный L1)
- Префикс всех записей L1 с «0», L1 становится {000, 001, 011, 010}
- Префикс всех записей L2 с «1», L2 становится {110, 111, 101, 100}
- Сцепив L1 и L2, получим {000, 001, 011, 010, 110, 111, 101,
100}
Первое решение приведено ниже (на основе приведенного выше примера решения).
но приведенное ниже решение не будет работать после 22,23 числа.
Произошла ошибка выделения памяти.
<?php
$input = 2;
$list_array = ["0","1"];
$reverse_array = array_reverse($list_array);
for($i = 1; $i < $input; $i++ )
{
for($j = 0; $j < sizeof($list_array); $j++)
{
$list_array[$j] = "0".$list_array[$j];
}
for($k = 0; $k < sizeof($reverse_array); $k++)
{
$reverse_array[$k] = "1".$reverse_array[$k];
}
$list_array = array_merge($list_array,$reverse_array);
$reverse_array = array_reverse($list_array);
}
for($l = sizeof($list_array) - $input; $l < sizeof($list_array); $l++)
{
print_r($list_array[$l]);
echo "<br />";
}
?>
Второе решение приведено ниже
Это решение будет работать до 63. После 63 это покажет ошибку тайм-аута.
Это будет работать до 63, когда 64-битный PHP работает на 64-битной ОС. если это 32-битный PHP, работающий на 64-битной ОС, он не будет работать после 31.
<?php
$n = 59;
$intial = pow(2, $n) - $n;
$length = pow(2, $n) - 1;
for($i= $intial; $i <= $length; $i++)
{
$decimal = ($i >> 1) ^ $i;
print_r(decbin($decimal));
echo "<br />";
}
?>
Пожалуйста, помогите мне найти это решение.
вопрос: как решить выше, включая $ n = 64 и $ n = 65
Решение
Это должно работать для вас:
<?php
print_r( getResult( 4 ) );
function getResult ( $n ) {
$result = [];
for ( $i = 0; $i < $n; $i++ ) {
$result[] = arr_xor(
str_split( str_pad( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), $n, '1', STR_PAD_LEFT ) ),
str_split( '0' . str_pad( substr( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), -1-(int)ceil(log($n - $i - 1, 2)), -1), $n - 1, '1', STR_PAD_LEFT ) )
);
}
return $result;
}
function arr_xor( $a, $b ) {
$result = [];
for ( $i = 0; $i < count( $a ); $i++ )
$result[] = (int)$a[$i] ^ (int)$b[$i];
return implode( '', $result );
}
Он просто использует формулу из вашего второго решения (($i >> 1) ^ $i), но так как вы не можете использовать это для целых чисел больше, чем PHP_INT_MAX, он использует массив с каждым элементом, представляющим один бит. Это не самое эффективное решение, но может легко выйти за рамки 65. $n = 1000 Кажется, нет проблем.
Другие решения
Другой ответ, и он похож на @paulpro, и это та же идея, которую я применил во втором решении. ($i >> 1) ^ $i
<?php
$n = 65;
for ( $i = 0; $i < $n; $i++ )
{
$decimal = decbin($n - $i - 1);
$replace = strtr( $decimal, '01', '10' );
$cast = (int)ceil(log($n - $i - 1, 2));
$padding = str_pad( $replace , $cast , '0', STR_PAD_LEFT );
$a_string = str_pad( $padding, $n, '1', STR_PAD_LEFT );
//shifting the bit to right
$substring = substr( $a_string , 0 , -1);
$b_string = str_pad( $substring , $n, '0', STR_PAD_LEFT );
$a = str_split( $a_string );
$b = str_split( $b_string );
for ( $j = 0; $j < count( $a ); $j++ )
{
print_r((int)$a[$j] ^ (int)$b[$j]);
}
echo "\n";
}
?>