IMHO.WS
Страница 1 из 3 1 23
Показывать 40 сообщений этой темы на одной странице

IMHO.WS (http://www.imho.ws/index.php)
-   Программирование (http://www.imho.ws/forumdisplay.php?f=40)
-   -   Задачки для программистов (http://www.imho.ws/showthread.php?t=57497)

Dimm 29.04.2004 12:22
Задачки для программистов
 
Да... заплесневели вы здесь ;)

Представляю ма-а-аленькие задачки для программистов на сообразительность.

Если никто не решает - правильный ответ через 2 дня.

1) Даны две переменные, ну например a и b. Скажем а = 5, b = 3.
Требуется: поменять местами их значения без объявления третьей (темповой) переменной.

2) Дан одностронний linked list. Требуется развернуть его. Естесственно красиво.

3) Дан вектор. Представте его как queue. Иначе говоря симулируйте очередь с помощью массива.


Приятного голово-ломания :winkgrin:

cousin AVI 29.04.2004 12:31
и на чем это дело надо реализовывать?кто на чем умеет?

Ghost 29.04.2004 12:33
Первая решается очень просто:
Код:
b := a + b;
a := b - a;
b := b - a;
И объясни, что есть 'linked list' - никогда с этим не сталкивался, а может и встречался, только называл иначе...

Ghost 29.04.2004 12:37
У меня тоже есть задачка на сообразительность: как вычислить максимальное значение целочисленных неотрицательных (типы byte, word) переменных a и b, не используя ветвления и циклов (на паскале)? Т.е. фактически найти max(a, b).

Gike 29.04.2004 12:38
задача #1:
пусть b>a иначе аналогично
a=(a+b)/2
b=b-a
a=a+b
b=a-2*b

пока набирал уже ответили.... :(

Merlin Cori 29.04.2004 12:40
Код:
$a=5;
$b=3;
$a=$a+$b;
$b=$a-$b;
$a=$a-$b;
echo "a= $a  b= $b";

Dimm 29.04.2004 15:21
cousin AVI
Дело не в языке, а в алгоритме. Можешь вообще на псевдокоде написать.

Ghost
linked list - связанный список. В типичной конфигурации, каждый елемент помимо даты имеет либо 2 указателя (двухсторонний список - prev и next) либо 1 указатель (одностронний список - next)

Gike
А на фига на 2 делить???

Dimm 29.04.2004 15:30
Цитата:
Сообщение от Ghost
У меня тоже есть задачка на сообразительность: как вычислить максимальное значение целочисленных неотрицательных (типы byte, word) переменных a и b, не используя ветвления и циклов (на паскале)? Т.е. фактически найти max(a, b).
А в чём проблема-то?
Возведи 2 в степень sizeof(byte) или sizeof(word) и т.д.

Gike 29.04.2004 15:30
Цитата:
Сообщение от Programmer
А на фига на 2 делить???
я решал начертив отрезок с координатами a и b
и дальше через середину и длину
a=(a+b)/2 - середина
b=b-a - половина длины
a=a+b
b=a-2*b

Ghost 29.04.2004 15:37
Programmer
А-а-а... Тады знаем-с. 2-ая задача (развернуть я так полагаю, преобразовать из 1->2->3 в 3->2->1) тоже решается просто. Писать прогу в ломы поэтому воспльзуюсь разрешением использовать псевдокод. ;)
Короче так. Пусть heap - голова списка, ^.info - поле, ^.next - ссылка на следующий элемент. Тогда:
  1. c := heap; p := nil;
  2. n := c^.next; c^.next := p; p := c; c := n;
  3. если c <> nil, то возвращаемся на пункт (2)
  4. heap := p;
Кажись так...

Ghost 29.04.2004 15:39
Programmer
Почитай внимательнее - надо написать прогу, которая выводит максимальное из двух чисел, но при этом не содержит ветвеления и циклов. ;)

Gike 29.04.2004 15:46
Max=(a+b+|a-b|)/2
Min=(a+b-|a-b|)/2

Ghost 29.04.2004 15:58
Gike
Молодца. :yees: Я первый раз тоже так решил. А теперь тоже самое без использования модуля?... ;)

Gike 29.04.2004 16:02
Ghost
Max=(a+b+sqrt((a-b)^2)/2
Min=(a+b-sqrt((a-b)^2)/2
:winkgrin:

Ghost 29.04.2004 16:09
Gike
Хитрый. Надеюсь не надо объяснять, что при извлечении корня с последующим возведением в степень не избежать ошибок, т.е. придется еще и извлекать целую часть или округлять - гемор. Чтоб не мучались, вот до чего дошел я:
Код:
c1 := ((1 - (b-a)) * (a xor b)) shr 15;
c2 := 1 - (a-b) shr 15;
max := c2 * a + c1 * b;

Gike 29.04.2004 16:27
Цитата:
Сообщение от Ghost
Gike
Хитрый. Надеюсь не надо объяснять, что при извлечении корня с последующим возведением в степень не избежать ошибок....
Это ясно:)
а на понимание твоего решения у меня явно нехватает знаний:lamer: :)

Dimm 29.04.2004 19:02
Ghost
Однозначно впереди. Ну а 3-ю задачу?

Dimm 29.04.2004 19:05
Ghost
Только вот решение с модулем гораздо лучше, потому что во 2-ом твоём решении есть маленький недочет: оно работает только для 16-битовых типов. И не будет работать для всех остальных. Так что...

Ghost 29.04.2004 19:11
А что третью? В моем понимании, вектор - одномерный массив (например, 1::2::3), а преобразовать его надо в списочек: 1->2->3. Это же стандартный алгоритм создания списка с головы (если просматривать массив с первого элемента) или с хвоста (если просматривать массив с конца), который рассказывается в первую очередь при изучении темы "Динамические структуры данных: связные списки". Я это и сам студентам рассказываю. Или я, может, задания не понял?...

По поводу решения без модуля: это действительно только для 16-битных чисел, просто я забыл это указать. Просто как-то раз возникла задача, написать такую прогу. Сперва написал с модулями, а мне говорят, мол, там все равно есть ветвление, хоть его и не видно - при вычислении модуля. Поэтому и придумал такой вот способ, хотя и к нему можно придраться - к сдвигу и xor'у... сказать, дескать, сдвиг на n бит - цикл, исключающее 'или' (т.е. xor) - ветвление. :(

Кстати, если я не ошибся в своем предположении насчет третьей задачи абзацем выше, то вот код:
Код:
uses
  crt;
type
  List = ^ListItem;
  ListItem = record
    info: integer;
    next: List;
  end;
const
  n = 10;
var
  a:    array [1..n] of integer;
  i:    integer;
  l, p: List;
begin
  clrscr;
  randomize;
  writeln ('vector:');
  for i := 1 to n do begin
    a[i] := random(100);
    write (a[i]:4);
  end;
  writeln;
  l := nil;
  for i := n downto 1 do begin
    new (p);
    p^.info := a[i];
    p^.next := l;
    l := p;
  end;
  writeln('list:');
  p := l;
  while p <> nil do begin
    write (p^.info:4);
    p := p^.next;
  end;
  writeln;
  readkey;
end.

a_ber 29.04.2004 19:25
Если хотите то одна из когда-то знаменитых Хайфских задач с курса "Структуры данных"--3й семестр--- ее потом любили на интервью спрашивать:
дан однонаправленный связный список. найти есть ли в нем петля и если есть то где ? (Будет решение может добавлю маленькое усложнение --- пока не буду подсказывать)

Ghost 29.04.2004 19:36
a_ber
Ну дык, иди по списку, запоминай адреса, по которым прошел, и проверяй наличие очередного адреса в списке запомненных. Если найдешь повторяющийся, значит нашел начало петли. Признаю, алгоритм - дубовый, но сработает. ;)

Может многие помнят по школе такую задачу: даны три натуральных числа - n, m и k. Необходимо найти k-ую цифру после запятой в десятичной дроби n/m. Я тут усложнил задачу и дал ее на недавно прошедшей в нашем ВУЗе олимпиаде - ни одна собака не решила. :) Короче, необходимо представить n/m в виде десятичной дроби с периодом (если есть). Например, 3/5=1.5, 1/30=0.0(3). Кто смогет? ;)

Dimm 29.04.2004 21:38
Ghost
Ошибка. Надо превратить в queue. Шапку исправил.

Dimm 29.04.2004 21:42
Ghost
Гы :) приколист. Твоё решение не эффективное. Если бы ты так ответил на интервью - хрен бы тебя взяли на работу.

f00rd 29.04.2004 22:28
Ghost

Решение задачи:

Код:
function MM(m1,m2:integer):string;
var
 i,k,l:integer;
 s,m,b,d,dudu:string;
 ok:boolean;
begin
 s:=FloatToStr(m1/m2);

 if pos(',',s)<=0 then
  begin
  Result:=s;
  exit;
  end;
 b:=copy(s,1,pos(',',s)-1);
 delete(s,1,pos(',',s));

 for i:=1 to Length(s) do
  begin
  for k:=1 to Length(s)-i do
    begin
    m:='';
    d:=s;
    delete(d,1,i-1);
    m:=copy(s,i,k);
    delete(d,1,Length(m));
    if pos(m,d)>0 then
      begin
      ok:=true;
      delete(d,(length(d) div Length(m))*Length(m),length(d));
      for l:=1 to (length(d) div Length(m)) do
        begin
        dudu:=copy(d,(l*Length(m))-(Length(m)-1),Length(m));
        if (Length(m)<=Length(d)-l*Length(m)) and (dudu<>m) then
          begin
          ok:=false;
          break;
          end;
        end;
      if ok then
        begin
        Result:=b+','+copy(s,1,i-1)+'('+m+')';
        exit;
        end;
      end;
    end;
  end;
end;
ф-ия, где m1 и m2 - числитель и знаменатель дроби...

В каком ты там вузе?

BRULIK 29.04.2004 23:10
a_ber
Pomoemy , esli vziat' dva ykazatelia i pustit' po spisky ... tol'ko odin (1) na sled. element a drygoy (2) cherez element, i proveriat' ih addresa ... esli odin iz ykazateley popal na Null znachit spisok ne zamknytiy , a esli addresa sovpali znachit est' petlia ...
t.e. ykazatel' (2) "dogonit" ykazatel' (1)
na listike vrode rabotaet ...

Dimm 30.04.2004 01:23
Ghost
А рекурсией слабо лист развернуть ? gigi

Код:
Node *ReverseList(Node *current, Node *parent)
{
  Node *temp;
  if(current == null)
      temp= parent;
  else
  {
      temp = ReverseList(current->next, current);
      current->next = parent;     
  }
  return temp;
}

Вызываем:
NewTail = ReverseList(tail, NULL);

Ghost 30.04.2004 11:27
Programmer
Цитата:
Твоё решение не эффективное. Если бы ты так ответил на интервью - хрен бы тебя взяли на работу.
Не эффективное - признаю. Немного подумав вечерком, придумал тоже что и BRULIK, т.е. на этот раз меня опередили. ;)
f00rd
Цитата:
В каком ты там вузе?
Воронежский Гос. Пед. Университет. Кафедра Информатики.
Оригинальное решение, но можно проще:
Код:
uses
  crt;
var
  n, m, p, k: byte;
  s, d:      string;
begin
  repeat
    clrscr;
    write ('n = '); readln (n);
    repeat
      write ('m = '); readln (m);
      if m = 0 then writeln ('error: m = 0!');
    until m > 0;
    k := n mod m;
    s := '';
    d := '';
    p := 255;
    while (p >= length(s)) and (k <> 0) do
      if pos(chr(k), d) <> 0 then begin
        p := pos(chr(k), d);
        s := Copy(s,1,p-1) + '(' + Copy(s,p,length(s)) + ')';
      end
      else begin
        s := s + chr (48 + ((10 * k) div m));
        d := d + chr (k);
        k := (10 * k) mod m;
      end;
    writeln ('n/m = ' , n div m, ',',s);
    writeln ('press ESC for exit..');
  until readkey = #27;
end.
Programmer
Цитата:
А рекурсией слабо лист развернуть ?
Не слабо. Люблю рекурсию. Только если задача элементарно решается без нее, то я ее стараюсь и не использовать. :)
А слабо выполнить эту же задачу в Прологе? ;)

alexey_ma 30.04.2004 20:02
2Programmer
Вполне можно обойтись одним параметром:
Код:
Node *ReverseList(Node *current)
{
        Node *temp;
        if(current->next==NULL)
                temp= current;
        else
        {
                temp = ReverseList(current->next);
                current->next->next=current;
                current->next=NULL; 
        }
        return temp;
}

Dimm 01.05.2004 00:13
BRULIK
Ghost
Уважаемые сэры. Ваше решение по поводу петли неправильное.
Дан лист:
a->b->c->d->e и петля e->b
начало:
p1 = a, p2 = c
шаги:
1. p1 = b, p2 = d
2. p1 = c, p2 = e
3. p1 = d, p2 = b
4. p1 = e, p2 = c
5. p1 = b, p2 = d
Видно, что уже на 5-ом шаге мы приходим в ситуацию 2-го шага. И так далее.
Да и посудите сами. С чего им догонять друг друга, если двигаются они с одинаковой скоростью. Расстояние между ними будет сохраняться.

Dimm 01.05.2004 00:53
BRULIK
Ghost

Весь прикол в том что они должны двигаться с разными скоростями. Чего вы в вашем решении не указали :)

Код:
Node* p1 = tail, *p2 = tail;
bool bLoop = false;
while ( p1 != NULL && p2 != NULL )
{
      p1 = p1->next;
      p2 = (p2->next != NULL) ? p2->next->next : NULL;
      if ( (bLoop = (p1==p2)) )
        break;
}
Вот шаги для того-же списка:
1. p1 = b, p2 = c
2. p1 = c, p2 = e
3. p1 = d, p2 = c
4. p1 = e, p2 = e --> FINISH

BRULIK 01.05.2004 16:22
ia tak i napisal
Цитата:
a drygoy (2) cherez element

Dimm 01.05.2004 18:01
brulik
Та как ты написал, не понятно, к чему относится "через один". К начальной позиции или к скорости.

/7y3uK 02.05.2004 00:57
ребяты... :) первую на асме не проробовали??
push & pop ка раз меняет местами значения ...
остальные - АСМ форева! нефиг пугать... если сообразительность заключается только в этом... по-моему ребята дали развернутые ответы...

Dimm 02.05.2004 01:25
/7y3uK
Если честно, из твоего поста мало что понял. Что ты хотел сказать?

2 All
Осталась 3-я задача (см. шапку). Если никто не решает, даю решение завтра.

a_ber 02.05.2004 12:43
По поводу задачи о петле:
а) Начало правильное, но я еще не видел где координата за линейное время?
б) Гост: линейной дополнительной памяти никто не давал ;)

Мне (и не тол'ко мне) нравится этот паттерн: 2 пойнтера движушиеся с разной скоростью --- он иногда красиво применим в разных задачах, помню что были, но не помню деталей...

в) Есть еще одно решение этой части задачи... кто найдет?

joker99 02.05.2004 20:30
Цитата:
Сообщение от Programmer
2 All
Осталась 3-я задача (см. шапку).
Ну так это просто:

берётся две интовые переменные (first_elem,first_empty). Одна указывает на первое занятое место в векторе, вторая на первое незанятое. Вначале обе указывают на 0. Также нужен флаг который говорит очередь пустая или полная, так как эти состояния рваны, с точки зрения указателей(first_elem == first_empty).
Добавление элемента:
Код:
if (queue_full == false)
{
  arr[first_empty] = elem;
  first_empty=(first_empty+1) % arr_size.;
  if (first_empty == first_elem)
    queue_full = true;
}
else
  return QUEUE_FULL_ERROR
Доставание элемента:
Код:
if (queue_full == true  || first_empty != first_elem)
{
  elem = arr[first_elem];
  first_elem=(first_elem+1) % arr_size.;
  queue_full = false;
}
else
  return QUEUE_EMPTY_ERROR
Вначале:
first_elem = first_empty = 0;
queue_full = false;

Dimm 02.05.2004 22:15
joker99
Ну скажем не совсем так. Вторая функция у тебя не правильна.
Во-первых когда ты
Цитата:
достаёшь элемент
иначе говоря делаешь dequeue() элемент должен удалятся из массива и продвигать надо другой индех. И кроме того, почему сразу
Цитата:
queue_full = false;
.
Вот правильная имплементация dequeue():
Я держу переменные head (продвигается вправо когда элемент достаётся), tail (продвигается вправо когда елемент кладут в очередь) и count (для контроля над количеством элементов).
Код:
Object dequeue()
{
    if ( count == 0 )
      throw new Exception("Queue is empty");
 
    Object result = array[head];
    array[head] = null;
    head = ++head % array.length;
    count--;

    return result;
}
Код enqueue() приводить не буду, посколько ты всё правильно написал. В моём случае двигался бы tail.

joker99 03.05.2004 00:10
Цитата:
элемент должен удалятся из массива
Почему должен?
Цитата:
продвигать надо другой индех.
Ну мой first_elem это и есть твой head, так что передвигаю я то что надо.
Цитата:
И кроме того, почему сразу queue_full = false;
Потому что queue_full обозначает у меня что очередь полная. А как только я из неё что-то достал, она перестаёт быть полной, т.е. queue_full = false вовсе не значит что очередь пустая. Это значит что очередь неполная.
Ну неподумал я использовать простой счётчик, а так мой алгоритм работает.

Dimm 03.05.2004 00:26
Цитата:
Почему должен?
Смотри определение очереди. Когда ты делаешь enqueue() ты добавляешь елемeнт в очередь, а когда делаешь dequeue() ты убираешь элемент из очереди. Подобно функции pop() у стака.

Цитата:
Ну мой first_elem это и есть твой head, так что передвигаю я то что надо
Здесь ты прав, мне просто показалось что в обоих случаях ты двигаешь first_elem. IMHO, first_elem и first_empty не совсем удачные имена для этих переменных.

joker99 03.05.2004 00:51
Цитата:
Смотри определение очереди
это уже скорее не определение очереди а имплементация, как я понимаю убирание элемента, это значит что следуюший dequeue() вернёт следуюший элемент. То есть физически элемент может остатся в масиве, но логически он уже не в очереди.
Тем более если елемент это не объект а value-type, то неизветно чем заполнят пустое место.


Часовой пояс GMT +4, время: 15:42.
Страница 1 из 3 1 23
Показывать 40 сообщений этой темы на одной странице

Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.