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

Модератор: Модераторы разделов

Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

Re: Задачки для разминки.

Сообщение sarutobi »

а мне вот пришло в голову такое:
как только встречаем 1 - делаем обход графа в ширину с заменой 1 на двойки.
граф закончился - увеличиваем счетчик островов на 1 и повторяем до конца массива
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

Re: Задачки для разминки.

Сообщение sarutobi »

А вот еще вспомнилась задачка....
Есть набор префиксов (A, AB, ABB...) таких, что ни один из префиксов не может встретиться в середине другого (совпадение возможно только в начале). Имеется строка произвольного вида. Необходимо найти максимально длинную подстроку, начинающуюся с первого символа строки и составленную из заданных префиксов.
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
Mage-Warrior
Сообщения: 869
Статус: Семь раз понюхай, один раз откуси!
ОС: SlackWare 12.1

Re: Задачки для разминки.

Сообщение Mage-Warrior »

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

Сегодня увидел эту задачку про острова. Подумал, что это еще и неплохой способ потренироваться в C++, который я с недавних пор изучаю. Вот думаю, нужно ли выкладывать решение? Вдруг, кому-то тоже захочется решить, а я тут соблазняю готовым. Ругаться никто не будет? Кстати, идея с нумерацией островов сработает, но мой алгоритм решает задачи, даже с ландшафтными островами (т.е. при использовании не только 0 и 1) :)
Вложения
islands.zip
(674 байт) 171 скачивание
*- Большинство проблем, дружок, завсегда покажет лог! -*
Спасибо сказали:
Аватара пользователя
Denjs
Сообщения: 1685
ОС: SuSe 10.2

Re: Задачки для разминки.

Сообщение Denjs »

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

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

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


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

:rolleyes:
QDroid - Среда исполнения и фреймворк для QtScript.
OTPD - Открытые драйвера промышленных принтеров чеков и этикеток (кроссплатформенная подсистема печати).
Спасибо сказали:
Аватара пользователя
Liksys
Сообщения: 2910

Re: Задачки для разминки.

Сообщение Liksys »

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

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

while (*t++==*s++);
Спасибо сказали:
Аватара пользователя
Red User
Сообщения: 229
ОС: Debian

Re: Задачки для разминки.

Сообщение Red User »

Denjs писал(а):
28.06.2007 21:50
ыыыы...
расскажите по шагам что делает инструкция

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

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


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

:rolleyes:


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

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


Если слева строки хватит, то всё будет нормально.
А ведь когда-то не боялись мы программы любой,
И с одним лишь debug'ом выходили на бой,
И искусно написанный вирус встречали как брата
Спасибо сказали:
Nikonik
Сообщения: 19

Re: Задачки для разминки.

Сообщение Nikonik »

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

У меня 512 байт
если с извращениями оптимизации размера - 399 байт
Вложения
task_obf.txt
(399 байт) 138 скачиваний
task.txt
(512 байт) 160 скачиваний
Спасибо сказали:
Аватара пользователя
wi:
Сообщения: 535
Статус: wi love linux
ОС: Open SuSE 11.0

Re: Задачки для разминки.

Сообщение wi: »

Ладно, я вот что еще вспомнил, совсем простая: поменять две переменные местами (числа) не используя третью.
Типа a=b; b=a;
%s
Спасибо сказали:
Аватара пользователя
Uncle_Theodore
Сообщения: 3339
ОС: Slackware 12.2, ArchLinux 64

Re: Задачки для разминки.

Сообщение Uncle_Theodore »

wi: писал(а):
10.08.2007 23:37
Ладно, я вот что еще вспомнил, совсем простая: поменять две переменные местами (числа) не используя третью.
Типа 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
Сообщения: 599
ОС: Archlinux

Re: Задачки для разминки.

Сообщение moog »

Да, на асме такую задачку решать надо, и без всяких велосипедов).
Спасибо сказали:
v04bvs
Сообщения: 636
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение v04bvs »

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

Это была моя самая первая задача по программированию! :) И я жутко горд, что в 7 классе сообразил как это сделать (тоже через +\-) :)
Спасибо сказали:
Аватара пользователя
wi:
Сообщения: 535
Статус: wi love linux
ОС: Open SuSE 11.0

Re: Задачки для разминки.

Сообщение wi: »

Uncle_Theodore писал(а):
10.08.2007 23:45

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

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

:cool:
%s
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

Re: Задачки для разминки.

Сообщение sarutobi »

две переменных обменять - это задачка со вступительных экзаменов :)
Можно попробовать вычислить строку "2+2*2" программно, если есть желание....
Этому алгоритму нас учили на 1 курсе....
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
tarkus
Сообщения: 38

Re: Задачки для разминки.

Сообщение tarkus »

x^=y^=x^=y

но это гораздо медленней чем через 3-ю
Ушел на прогулку до выхода KDE4. Всем удачи! :)
Спасибо сказали:
Аватара пользователя
Uncle_Theodore
Сообщения: 3339
ОС: Slackware 12.2, ArchLinux 64

Re: Задачки для разминки.

Сообщение Uncle_Theodore »

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

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

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

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

Найдите алгоритм Доброго Дядюшки.
Спасибо сказали:
Аватара пользователя
wi:
Сообщения: 535
Статус: wi love linux
ОС: Open SuSE 11.0

Re: Задачки для разминки.

Сообщение wi: »

офф: юзать почту а-ля голубей :)
но вот на ссылочку я погуглил: http://subway.net.ru/diary/20.07.2003/3
завтра проснусь к обду и буду думать над решением :)))
%s
Спасибо сказали:
Аватара пользователя
begemot.
Сообщения: 161
ОС: GNU
Контактная информация:

Re: Задачки для разминки.

Сообщение begemot. »

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

x=1, y=1?
Нагуглил статью об этом - исключающее или.
Алкоголь - наркотический пост-плазматический яд.
Тюремная смертность в три (!!!) раза ниже, чем на свободе, поскольку в тюрьмах запрещён алкоголь! статистика МВД
Спасибо сказали:
Аватара пользователя
Voice
Сообщения: 1073
Статус: столлманист
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Voice »

Uncle_Theodore писал(а):
15.08.2007 03:35
Найдите алгоритм Доброго Дядюшки.

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

И еще, второй вариант.
Есть алгоритм, забыл как называется :(, там по открытому каналу абоненты
передают друг другу открытые числа, а закрытые знают только они. И на основе пересланых чисел генерируются ключи.
(Сейчас времени нету, потом найду название алгоритма).
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
Спасибо сказали:
Аватара пользователя
Voice
Сообщения: 1073
Статус: столлманист
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Voice »

Вот, нашел, это Алгоритм Диффи — Хеллмана.
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B0%D0%BD%D0%B0
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

Re: Задачки для разминки.

Сообщение sarutobi »

Блин, алгоритм Доброго Дядюшки примитивен донельзя.
А насчет пары чисел это криптография с открытым и закрытым ключом, базирующаяся на малой теореме Ферма, насколько я помню.
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
wi:
Сообщения: 535
Статус: wi love linux
ОС: Open SuSE 11.0

Re: Задачки для разминки.

Сообщение wi: »

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

И еще, я так понимаю, что для for ключи расчитываются единожды при старте, например, для for (i=0; i<n; i++), если n заменить на сложную функцию, ее результат будет выщитываться всего лишь один раз, а для while эта функция будет просчитываться заново каждый цикл. Я прав?
%s
Спасибо сказали:
Аватара пользователя
Voice
Сообщения: 1073
Статус: столлманист
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Voice »

Думаю что все зависит от компилятора. Компилятор компилятору рознь.
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
Спасибо сказали:
Аватара пользователя
BlackStar
Сообщения: 1338
Статус: We are all Kosh
ОС: Fedora 10
Контактная информация:

Re: Задачки для разминки.

Сообщение BlackStar »

Uncle_Theodore, вот уже почти 2 месяца прошло, а ответа все нет ): Может покажите как надо?
LightLang Team
Спасибо сказали:
v04bvs
Сообщения: 636
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение v04bvs »

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

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

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

нет. for тоже просчитывается при каждом цикле.
Спасибо сказали:
Аватара пользователя
Uncle_Theodore
Сообщения: 3339
ОС: Slackware 12.2, ArchLinux 64

Re: Задачки для разминки.

Сообщение Uncle_Theodore »

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

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

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

Re: Задачки для разминки.

Сообщение v04bvs »

Uncle_Theodore писал(а):
08.10.2007 20:35
BlackStar писал(а):
08.10.2007 12:04
Uncle_Theodore, вот уже почти 2 месяца прошло, а ответа все нет ): Может покажите как надо?

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

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

Чего то я не понял. Вы написали решение и тут же опровергли его :) Какое же истинное решение то?
Спасибо сказали:
apacho
Сообщения: 110
ОС: MOPSLinux 5.1

Re: Задачки для разминки.

Сообщение 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
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

Re: Задачки для разминки.

Сообщение Crazy »

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

Desipere in loco
Спасибо сказали:
Аватара пользователя
Subj
Сообщения: 151
Статус: Useful
ОС: win

Re: Задачки для разминки.

Сообщение Subj »

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


Отчегож? Вполне правильное решение. Я тоже об этом подумал. Вот моя реализация (на Ада):
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
Building better software with Ada
Спасибо сказали:
Аватара пользователя
Subj
Сообщения: 151
Статус: Useful
ОС: win

Re: Задачки для разминки.

Сообщение Subj »

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