Задачки для разминки. (Простенькие такие...)

[sarutobi]

а мне вот пришло в голову такое:
как только встречаем 1 - делаем обход графа в ширину с заменой 1 на двойки.
граф закончился - увеличиваем счетчик островов на 1 и повторяем до конца массива

[sarutobi]

А вот еще вспомнилась задачка....
Есть набор префиксов (A, AB, ABB...) таких, что ни один из префиксов не может встретиться в середине другого (совпадение возможно только в начале). Имеется строка произвольного вида. Необходимо найти максимально длинную подстроку, начинающуюся с первого символа строки и составленную из заданных префиксов.

[Mage-Warrior]

Старая задачка, обычно на школьных районных олимпиадах ее дают:
Имеется матрица (n*m) заполненная 1 и 0. Единицы - это острова море, а нули - море. Если единицы находятся рядом по горизонтали или вертикали - то они образуют один остров. Найти количество островов.
P.S. Естественно могут быть "гнутые" и "дырявые" острова.
P.P.S. Как не странно, но решают ее редко, хотя она легкая.

Сегодня увидел эту задачку про острова. Подумал, что это еще и неплохой способ потренироваться в C++, который я с недавних пор изучаю. Вот думаю, нужно ли выкладывать решение? Вдруг, кому-то тоже захочется решить, а я тут соблазняю готовым. Ругаться никто не будет? Кстати, идея с нумерацией островов сработает, но мой алгоритм решает задачи, даже с ландшафтными островами (т.е. при использовании не только 0 и 1)

[Denjs]

ыыыы...
расскажите по шагам что делает инструкция

Код: Выделить всё

 while (*t++=*s++);

t и s - "строки"

[Liksys]

В таком виде будет сегфолтиться. Надо так:

Код: Выделить всё

while (*t++==*s++);

[Red User]

ыыыы...
расскажите по шагам что делает инструкция

Код: Выделить всё

 while (*t++=*s++);

t и s - "строки"

Это копирование строки. t и s должны иметь тип char*. Указатель s увеличивается на размера того типа, на который он указывает, постфиксно, то есть возвращается ещё не увеличенное значение (a = 1; n = a++; // после этого n == 1, a == 2). *s возвращает символ, на который указывает s. Тоже самое делается слева с t. После этого в область памяти, на которую указывает t, копируется символ, на который указывает s. Если этот символ не равен нулю, то цикл повторяется. Тело цикла пустое, выполняется только проверка на неравенство нулю того, что в скобках после while.

В таком виде будет сегфолтиться.

Если слева строки хватит, то всё будет нормально.

[Nikonik]

На задачу про острова можно посревноваться по размеру решения

У меня 512 байт
если с извращениями оптимизации размера - 399 байт

[wi:]

Ладно, я вот что еще вспомнил, совсем простая: поменять две переменные местами (числа) не используя третью.
Типа a=b; b=a;

[Uncle_Theodore]

Ладно, я вот что еще вспомнил, совсем простая: поменять две переменные местами (числа) не используя третью.
Типа a=b; b=a;

Код: Выделить всё

teddy@laptop~$ a=2
teddy@laptop~$ b=3
teddy@laptop~$ a=$((a-b))
teddy@laptop~$ b=$((a+b))
teddy@laptop~$ a=$((b-a))
teddy@laptop~$ echo $a
3
teddy@laptop~$ echo $b
2

С побайтовым XOR, конечно, забавнее...

[moog]

Да, на асме такую задачку решать надо, и без всяких велосипедов).

[v04bvs]

Ладно, я вот что еще вспомнил, совсем простая: поменять две переменные местами (числа) не используя третью.
Типа a=b; b=a;

Это была моя самая первая задача по программированию! И я жутко горд, что в 7 классе сообразил как это сделать (тоже через +\-)

[wi:]

Код: Выделить всё

teddy@laptop~$ a=2
teddy@laptop~$ echo $a

С побайтовым XOR, конечно, забавнее...

А я про такие возможности консоли и не знал Респект

Код: Выделить всё

wi@localhost:~$ a=linuxforum.ru
wi@localhost:~$ ping $a
PING linuxforum.ru (88.212.197.154) 56(84) bytes of data.
64 bytes from www.linuxforum.ru (88.212.197.154): icmp_seq=1 ttl=55 time=67.4 ms
64 bytes from www.linuxforum.ru (88.212.197.154): icmp_seq=2 ttl=55 time=99.1 ms
64 bytes from www.linuxforum.ru (88.212.197.154): icmp_seq=3 ttl=55 time=118 ms

[sarutobi]

две переменных обменять - это задачка со вступительных экзаменов
Можно попробовать вычислить строку "2+2*2" программно, если есть желание....
Этому алгоритму нас учили на 1 курсе....

[tarkus]

x^=y^=x^=y

но это гораздо медленней чем через 3-ю

[Uncle_Theodore]

Вот вам еще задачка. Посложнее.

Алиса хочет послать Бобу важное тайное сообщение. К сожалению, канал, по которому они общаются, прослушивается Гэбней Кровавой, а у Алисы и Боба есть только возможность шифровать сообщения посредством XOR-инья с ключом произвольной длины на своих компьютерах.

То есть, Алиса может заXORить свое сообщение и передать Бобу, и Боб может заXORить какое-нибудь сообщение и передать Алисе, но ключи свои они передать друг другу не могут. И даже не могут сообщить друг другу, какой длины эти ключи.

Алиса и Боб в отчаянии. Но Добрый Дядюшка знает алгоритм, по которому Алиса может послать Бобу свое сообщение, а Боб прочитать его, не используя ничего, кроме указанных средств.

Найдите алгоритм Доброго Дядюшки.

[wi:]

офф: юзать почту а-ля голубей
но вот на ссылочку я погуглил: http://subway.net.ru/diary/20.07.2003/3
завтра проснусь к обду и буду думать над решением ))

[begemot.]

После выполнения следующего кода на C, что находится в переменных x и y?
х=1
у=2
...

x=1, y=1?
Нагуглил статью об этом - исключающее или.

[Voice]

Найдите алгоритм Доброго Дядюшки.

Может он использует то свойство ксоринга, что он операция оборотная?
Тоесть, сообщение шифруется известным им обоим ключом и ним же расшифровывается?

И еще, второй вариант.
Есть алгоритм, забыл как называется , там по открытому каналу абоненты
передают друг другу открытые числа, а закрытые знают только они. И на основе пересланых чисел генерируются ключи.
(Сейчас времени нету, потом найду название алгоритма).

[Voice]

Вот, нашел, это Алгоритм Диффи — Хеллмана.
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B0%D0%BD%D0%B0

[sarutobi]

Блин, алгоритм Доброго Дядюшки примитивен донельзя.
А насчет пары чисел это криптография с открытым и закрытым ключом, базирующаяся на малой теореме Ферма, насколько я помню.

[wi:]

А вот такой вопрос: что быстрее, -- foreach, for или while ? Например, если нужно массив перебрать.

И еще, я так понимаю, что для for ключи расчитываются единожды при старте, например, для for (i=0; i<n; i++), если n заменить на сложную функцию, ее результат будет выщитываться всего лишь один раз, а для while эта функция будет просчитываться заново каждый цикл. Я прав?

[Voice]

Думаю что все зависит от компилятора. Компилятор компилятору рознь.

[BlackStar]

Uncle_Theodore, вот уже почти 2 месяца прошло, а ответа все нет ): Может покажите как надо?

[v04bvs]

А вот такой вопрос: что быстрее, -- foreach, for или while ? Например, если нужно массив перебрать.

На этот вопрос нет ответа. Более того, сам вопрос не должен возникать. Если есть необходимость оптимизировать до такой степени - значит пора переходить на ассемблер.

И еще, я так понимаю, что для for ключи расчитываются единожды при старте, например, для for (i=0; i<n; i++), если n заменить на сложную функцию, ее результат будет выщитываться всего лишь один раз, а для while эта функция будет просчитываться заново каждый цикл. Я прав?

нет. for тоже просчитывается при каждом цикле.

[Uncle_Theodore]

Uncle_Theodore, вот уже почти 2 месяца прошло, а ответа все нет ): Может покажите как надо?

Дык, да тупо же...
Алиса XORит своё сообщение со своим ключом и передает Бобу.
Боб XORит полученное сообщение со своим ключом и передает Алисе.
Алиса XORит полученное от Боба сообщение со своим ключом и передает обратно Бобу.
Боб XORит полученное сообщение со своим ключом и читает сообщение от Алисы.

У этой задачи есть продолжение. Если Вы -- Гебешник Кровавый, как Вы сможете перехватить и расшифровать переписку Алисы и Боба? А ответ простой. Мониторьте их обмен информацией и перехватывайте все сообщения одинаковой длины. ПроXORив друг с другом два последовательных сообщения, Вы получите один из ключей...

[v04bvs]

Uncle_Theodore, вот уже почти 2 месяца прошло, а ответа все нет ): Может покажите как надо?

Дык, да тупо же...
Алиса XORит своё сообщение со своим ключом и передает Бобу.
Боб XORит полученное сообщение со своим ключом и передает Алисе.
Алиса XORит полученное от Боба сообщение со своим ключом и передает обратно Бобу.
Боб XORит полученное сообщение со своим ключом и читает сообщение от Алисы.

У этой задачи есть продолжение. Если Вы -- Гебешник Кровавый, как Вы сможете перехватить и расшифровать переписку Алисы и Боба? А ответ простой. Мониторьте их обмен информацией и перехватывайте все сообщения одинаковой длины. ПроXORив друг с другом два последовательных сообщения, Вы получите один из ключей...

Чего то я не понял. Вы написали решение и тут же опровергли его Какое же истинное решение то?

[apacho]

А вот мой код по островам:

#include <iostream>
using namespace std;

int main()
{
int hit=2,i=0,j=0,p=0,g=0,f=-1,k=0;
int s[m][n]=
{
{1,1,1,1,1,1},
{1,0,0,0,0,1},
{1,1,0,1,0,1},
{1,0,0,0,0,1},
{1,0,1,0,0,1},
{1,1,1,1,1,1}
};
for (;;)
{
for (i=0;i<n & j<m;++i)
{
if (k==1) {
if (s[j][i]==1) {
if (s[j][i-1]==hit) s[j][i]=hit;
if (s[j-1][i]==hit) s[j][i]=hit;
}
if (s[j][i]==hit)
{
if (s[j][i-1]==1) s[j][i-1]=hit;
if (s[j-1][i]==1) s[j-1][i]=hit;
}
}
if (s[j][i]==1 && k==0) {s[j][i]=hit;k=1;}
if (i==n-1) {++j;i=-1;}
}++hit;f+=1;
if (k==0) break;
k=0;
j=0;
}
cout << f;
}

За место m и n числа нужно подставить!

[Crazy]

С островом есть тупое решение. Взять рекурсивную функцию, которая будет удалять остров.
Перебираем массив, находим остров, увеличиваем счетчик, и удаляем остров.

[Subj]

С островом есть тупое решение. Взять рекурсивную функцию, которая будет удалять остров.
Перебираем массив, находим остров, увеличиваем счетчик, и удаляем остров.

Отчегож? Вполне правильное решение. Я тоже об этом подумал. Вот моя реализация (на Ада):
isl.adb

Код: Выделить всё

-----------------------------------------------------------------------
--   Copyright (C) 2008 by Gavrikov Valeriy                          --
--   subjrs@gmail.com                                                --
-----------------------------------------------------------------------

with Ada.Text_IO,
     Ada.Command_Line,
     Ada.Numerics.Discrete_Random;
use  Ada.Text_IO;

procedure Isl is

   subtype Element is Integer range 0 .. 1;
   package Element_Random is new Ada.Numerics.Discrete_Random(Element);
   use Element_Random;
   G : Generator;

   subtype N_Range is Integer range 1 .. Integer'Value(Ada.Command_Line.Argument(1)); -- V
   subtype M_Range is Integer range 1 .. Integer'Value(Ada.Command_Line.Argument(2)); -- H
   type Map_Type is array(N_Range, M_Range) of Integer;
   Map : Map_Type;

   procedure Stage_Print(i, j : Integer) is
   begin
      Put(Map(i, j)'Img);
   end Stage_Print;

   Is_Rec : Boolean := False;
   Count : Integer := 0;

   procedure Stage_Renumber(i, j : Integer) is
   begin
      if Map(i, j) = 1 then
         if not Is_Rec then
            Count := Count + 1;
            Is_Rec := True;
         end if;
         Map(i, j) := 0;
         -- Left
         if j > M_Range'First and then Map(i, j - 1) = 1 then
            Stage_Renumber(i, j - 1);
         end if;
         -- Up
         if i > N_Range'First and then Map(i - 1, j) = 1 then
            Stage_Renumber(i - 1, j);
         end if;
         -- Right
         if j < M_Range'Last  and then Map(i, j + 1) = 1 then
            Stage_Renumber(i, j + 1);
         end if;
         -- Down
         if i < N_Range'Last  and then Map(i + 1, j) = 1 then
            Stage_Renumber(i + 1, j);
         end if;
      end if;
   end Stage_Renumber;

   type Stage_Access  is access procedure(i, j : Integer);

   procedure Map_Loop(Stage : Stage_Access) is
   begin
      for i in N_Range loop
         for j in M_Range loop
            if Stage = Stage_Renumber'Access then
               Is_Rec := False;
            end if;
            Stage.All(i, j);
         end loop;
         if Stage = Stage_Print'Access then
            New_Line;
         end if;
      end loop;
   end Map_Loop;

begin
   Reset(G);
   Map := (others => (others => (Random(G))));
   Map_Loop(Stage_Print'Access);
   Map_Loop(Stage_Renumber'Access);
   New_Line;
   Put_Line(Count'Img);
end Isl;

Принимает два параметра(высота и ширина), рандомно генерит таблицу и выводит результат.
$ gnatmake isl
gcc -c isl.adb
gnatbind -x isl.ali
gnatlink isl.ali

$ ./isl 3 5
0 0 1 0 1
0 1 0 0 0
1 1 0 1 1

4
$ ./isl 6 2
1 0
0 1
1 0
1 1
0 0
0 0

3

[Subj]

А вот еще задачка из классики:
Найти все способы расположения восьми ферзей на шахматной доске так, чтобы они не били друг друга.
В свое время великий Гаус математически доказал что их 92 (способа).