Задачка для разминки мозга

← →
Inovet © (2014-04-30 14:57) [240]

Да, вывод:
{V,e,r,y, ,p,r,e,t,t,y, ,l,i,s,t} {} {L} {L and 2} {S,h,L}

← →
MBo © (2014-04-30 15:06) [241]

>Inovet
Идея понятна, но форматирование для случая "больше двух" не то

← →
Inovet © (2014-04-30 15:31) [242]

> [241] MBo © (30.04.14 15:06)
> но форматирование для случая "больше двух" не то

А, там же надо тоже "и", ну тогда ещё проще - достаточно 2 последних помнить

Вывод:
{V,e,r,y, ,p,r,e,t,t,y, ,l,i,s and t} {} {L} {L and 2} {S,h and L}

Так есть ли способ "не тупо"?

← →
Inovet © (2014-04-30 15:37) [243]

> [242] Inovet © (30.04.14 15:31)

Ну и второй тупой вариант более "медленный" - подставлять разделитель прямо в цикле, например, по значению счётчика.

← →
SergP © (2014-04-30 22:28) [244]

> Дана квадратная матрица NxN, содержащая единицы и нули.
> Требуется без использования дополнительной памяти (т.е.
> с O(1)) обнулить те столбцы и строки, в которых есть нули.
>

А тип данных в матрице позволяет присваивать элементам матрицы значения отличные от 0 и 1 ?

← →
MBo © (2014-05-01 07:23) [245]

>А тип данных в матрице позволяет присваивать элементам матрицы значения отличные от 0 и 1 ?

Нет

← →
Inovet © (2014-05-01 09:39) [246]

> [236] MBo © (30.04.14 13:28)
> Zero-Matrix

Идём по диагонали, смотрим стороны текущей матрицы. Если встречается 0, сбрасываем в 0 уже пройденные элементы строки или столбца. Т.о. дополнительная память не требуется, и внесённые изменения не влияют на результат.

Вроде, так должно работать.

← →
SergP © (2014-05-01 11:24) [247]

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

Далее проходим по всем строкам, кроме строки N
если в строке есть нулевой элемент, обнуляем строку, если нет - то копируем на ее место строку N

// пусть массив у нас будет Arr[0..xmax,0..ymax] // var // f1,f2:boolean; // x,y,i,j,n:integer; // ищем строку где нет нулевых элеменетов f2:=false; for y:=0 to ymax do begin f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then f1:=false; if f1 then begin n:=y; // если такая строка существует то запоминаем ее в N f2:=true; break; end; end; if f2 then begin // строка где нет нулевых элементов существует, ее номер в N // проверяем все столбцы на наличие нулевых элементов // for x:=0 to xmax do begin f1:=false; for j:=0 to ymax do if Arr[x,j]=0 then f1:=true; // если в столбще есть нулевые элементы то обнуляем соответствующий элемент в строке N if f1 then Arr[x,n]:=0; end; // проходим все строки кроме строки N for y:=0 to ymax do begin if y=n then continue; f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then f1:=false; // Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0; end; // если в каждой строке имеются нулевые элементы то обнуляем весь массив end else for x:=0 to xmax do for y:=0 to ymax do Arr[x,y]:=0;

← →
SergP © (2014-05-01 11:39) [248]

ну можно еще немного оптимизировать, увеличивши размер кода.

Во первых, заменить подобные вещи (проверка строки или столбца на наличие нулевых элементов:
вместо:
f1:=false; for j:=0 to ymax do if Arr[x,j]=0 then f1:=true;

написать:
f1:=false; for j:=0 to ymax do if Arr[x,j]=0 then begin f1:=true; break; end;

ну и не проверять повторно строки от 0 до N во второй части:
for y:=0 to ymax do begin if y=n then continue; f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then f1:=false; // Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0; end;

а сразу их обнулять:
for y:=0 to ymax do begin if y=n then continue; if y<0 then for i:=0 to xmax do a[i,y]:=0 else begin f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then f1:=false; // Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0; end; end;

← →
SergP © (2014-05-01 11:44) [249]

типа так:
// ищем строку где нет нулевых элеменетов f2:=false; for y:=0 to ymax do begin f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then begin f1:=false; break; end; if f1 then begin n:=y; // если такая строка существует то запоминаем ее в N f2:=true; break; end; end; if f2 then begin // строка где нет нулевых элементов существует, ее номер в N // проверяем все столбцы на наличие нулевых элементов // for x:=0 to xmax do begin f1:=false; for j:=0 to ymax do if Arr[x,j]=0 then begin f1:=true; break; end; // если в столбще есть нулевые элементы то обнуляем соответствующий элемент в строке N if f1 then Arr[x,n]:=0; end; // проходим все строки кроме строки N for y:=0 to ymax do begin if y=n then continue; if y<0 then for i:=0 to xmax do Arr[i,y]:=0 else begin f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then begin f1:=false; break; end; // Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0; end; end; // если в каждой строке имеются нулевые элементы то обнуляем весь массив end else for x:=0 to xmax do for y:=0 to ymax do Arr[x,y]:=0;

← →
SergP © (2014-05-01 11:46) [250]

хм. ошибка небольшая.

вот так нужно:

// ищем строку где нет нулевых элеменетов f2:=false; for y:=0 to ymax do begin f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then begin f1:=false; break; end; if f1 then begin n:=y; // если такая строка существует то запоминаем ее в N f2:=true; break; end; end; if f2 then begin // строка где нет нулевых элементов существует, ее номер в N // проверяем все столбцы на наличие нулевых элементов // for x:=0 to xmax do begin f1:=false; for j:=0 to ymax do if Arr[x,j]=0 then begin f1:=true; break; end; // если в столбще есть нулевые элементы то обнуляем соответствующий элемент в строке N if f1 then Arr[x,n]:=0; end; // проходим все строки кроме строки N for y:=0 to ymax do begin if y<n then for i:=0 to xmax do Arr[i,y]:=0; if y>n then begin f1:=true; for i:=0 to xmax do if Arr[i,y]=0 then begin f1:=false; break; end; // Если в строке нет нулевых элементов, заменяем ее копией строки N, иначе обнуляем for x:=0 to xmax do if f1 then Arr[x,y]:=Arr[x,n] else Arr[x,y]:=0; end; end; // если в каждой строке имеются нулевые элементы то обнуляем весь массив end else for x:=0 to xmax do for y:=0 to ymax do Arr[x,y]:=0;

← →
Sha © (2014-05-01 12:50) [251]

const h= 4; type TElement= byte; var m: array[0..h, 0..h] of TElement= ( (1, 0, 1, 1, 0), (0, 1, 1, 1, 0), (1, 1, 1, 1, 1), (1, 0, 1, 1, 1), (1, 1, 1, 1, 1)); procedure TForm1.Button3Click(Sender: TObject); var col0: TElement; i, j: integer; begin; col0:=1; for i:=0 to h do begin; if m[i,0]=0 then col0:=0; for j:=1 to h do if m[i,j]=0 then begin; m[i,0]:=0; m[0,j]:=0; end; end; for j:=1 to h do if m[0,j]=0 then for i:=1 to h do m[i,j]:=0; for i:=0 to h do if m[i,0]=0 then for j:=1 to h do m[i,j]:=0; if col0=0 then for i:=0 to h do m[i,0]:=0; //for i:=0 to h do Memo1.Lines.Add(Format("%d %d %d %d %d", // [m[i,0],m[i,1],m[i,2],m[i,3],m[i,4]])); end;

← →
Гора Фудзияма (2014-05-05 15:19) [252]

Удалено модератором

← →
KSergey © (2014-05-06 12:52) [253]

> Rouse_ © (16.04.14 23:26) [26]
> Result := (A * B - 6930 + (A xor B) - 23) <> 0;

Byte * Byte дает Integer ??
сволочи

← →
Sha © (2014-05-07 20:26) [254]

> KSergey © (06.05.14 12:52) [253]

Это так для всей арифметики, а если один операнд int64 - то и результат int64.
Для логики иначе.

← →
Sha © (2014-05-07 21:55) [255]

function Not1(a: byte): integer; begin; Result := not (a or 0); //= not byte(a) end; function Not2(a: byte): integer; begin; Result := not (a+0); //неожиданный, но соответствующий описанию результат = not integer(a) end; function Shl1(a: byte): integer; begin; Result := byte(a shl 8); //=byte(integer(a) shl 8) end; function Shl2(a: byte): integer; begin; Result := a shl 8; //ожидаемый, но не соответствующий описанию результат = integer(a) shl 8 end; procedure TForm1.Button8Click(Sender: TObject); begin; ShowMessage(IntToStr(Not1(1))); ShowMessage(IntToStr(Not2(1))); ShowMessage(IntToStr(Shl1(1))); ShowMessage(IntToStr(Shl2(1))); end;

Не поднять ли нам ветку?

За один проход по элементам целочисленного массива найти 0..5 непарных чисел.

Это типа намек как решать [208].

← →
han_malign (2014-05-15 12:52) [257]

> За один проход по элементам целочисленного массива найти 0..5 непарных чисел.

{1 shl k, 1 shl m, 1 shl k + 1 shl m, n, n}
- ну нету медианы...

вроде и не требуется она для решения

← →
Дмитрий СС (2014-05-15 18:36) [259]

А была тут такая задача:
Известны A и B:
A = x xor y
B = x + y
Найти x и y.

> Дмитрий СС (15.05.14 18:36) [259]

может получиться довольно много решений

← →
han_malign (2014-05-16 08:50) [261]

> вроде и не требуется

- в задаче о 2-х - медиана - это один из битов разницы, по которому надо делить свертку выборки...
позволяет обойтись честным O(1) по памяти(с двумя проходами)

- свертка по всем срезам [бит,значение] - вроде позволяет найти все значения(и не факт что 5 - предел)...
но если по правильному(N => ∞) - это все-таки O(ln N) - по памяти...
(т.к. с таким же успехом можно заявить, что 512 Mб битовая строка - это O(1) - т.к. не зависит от N)

> han_malign (16.05.14 08:50) [261]

Тем не менее это ничуть не мешает решает решить задачу поиска трех чисел ценой увеличения количества проходов или памяти в b раз (b - количество используемых битов в числах).

По моим экспериментам, похожим образом задача решается для 4, 5 и 6 чисел. Дальше не смотрел, т.к. там довольно громоздко все получается и в лоб уже не выходит вроде.

Для 4 чисел есть строгое доказательство и решение в 1 проход. Небольшой намек на решение дан в конце статьи в блоге.

Задачка для разминки мозга Найти похожие ветки