Задачки для программистов

[Dimm]

Да... заплесневели вы здесь

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

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

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

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

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


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

и на чем это дело надо реализовывать?кто на чем умеет?

[Ghost]

Первая решается очень просто:

b := a + b;
a := b - a;
b := b - a;

И объясни, что есть 'linked list' - никогда с этим не сталкивался, а может и встречался, только называл иначе...

[Ghost]

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

[Gike]

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

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

[Merlin Cori]

$a=5;
$b=3;
$a=$a+$b;
$b=$a-$b;
$a=$a-$b;
echo "a= $a  b= $b";

[Dimm]

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

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

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

[Dimm]

Сообщение от Ghost

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

А в чём проблема-то?
Возведи 2 в степень sizeof(byte) или sizeof(word) и т.д.

[Gike]

Сообщение от Programmer

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

я решал начертив отрезок с координатами a и b
и дальше через середину и длину
a=(a+b)/2 - середина
b=b-a - половина длины
a=a+b
b=a-2*b

[Ghost]

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]

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

[Gike]

Max=(a+b+|a-b|)/2
Min=(a+b-|a-b|)/2

[Ghost]

Gike
Молодца. Я первый раз тоже так решил. А теперь тоже самое без использования модуля?...

[Gike]

Ghost
Max=(a+b+sqrt((a-b)^2)/2
Min=(a+b-sqrt((a-b)^2)/2

[Ghost]

Gike
Хитрый. Надеюсь не надо объяснять, что при извлечении корня с последующим возведением в степень не избежать ошибок, т.е. придется еще и извлекать целую часть или округлять - гемор. Чтоб не мучались, вот до чего дошел я:

c1 := ((1 - (b-a)) * (a xor b)) shr 15;
c2 := 1 - (a-b) shr 15;
max := c2 * a + c1 * b;

[Gike]

Сообщение от Ghost

Gike
Хитрый. Надеюсь не надо объяснять, что при извлечении корня с последующим возведением в степень не избежать ошибок....

Это ясно
а на понимание твоего решения у меня явно нехватает знаний

[Dimm]

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

[Dimm]

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

[Ghost]

А что третью? В моем понимании, вектор - одномерный массив (например, 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]

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