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

[Ghost]

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

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

[Dimm]

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

[Dimm]

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

[f00rd]

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]

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]

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]

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]

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]

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]

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]

ia tak i napisal

a drygoy (2) cherez element

[Dimm]

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

[/7y3uK]

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

[Dimm]

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

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

[a_ber]

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

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

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

[joker99]

Сообщение от 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]

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]

элемент должен удалятся из массива

Почему должен?

продвигать надо другой индех.

Ну мой first_elem это и есть твой head, так что передвигаю я то что надо.

И кроме того, почему сразу queue_full = false;

Потому что queue_full обозначает у меня что очередь полная. А как только я из неё что-то достал, она перестаёт быть полной, т.е. queue_full = false вовсе не значит что очередь пустая. Это значит что очередь неполная.
Ну неподумал я использовать простой счётчик, а так мой алгоритм работает.

[Dimm]

Почему должен?

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

Ну мой first_elem это и есть твой head, так что передвигаю я то что надо

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

[joker99]

Смотри определение очереди

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