Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.06.2010, 16:16   #1
Maksik
Пользователь
 
Регистрация: 24.06.2009
Сообщений: 14
По умолчанию Двоичные деревья.

Прошу помощи в задании.
Используя структуру данных бинарное дерево поиска решить следующую задачу: Даны две последовательности чисел: A и B, полученные по следующему закону:
Последовательность A задаётся по следующим формулам:
Ai = seedAi mod 1000000,
где seedAi для i > 1 вычисляется как:
seedAi = (seedAi-1 * multiplierA + addendA) mod divisorA
Последовательность B задана по схожим формулам:
Bi = seedBi mod 1000000,
где seedBi для i > 1 вычисляется как:
seedBi = (seedBi-1 * multiplierB + addendB) mod divisorB

Из последоветельности A выписываем NA чисел
Из последоветельности B выписываем NB чисел
Вычёркивает из них [последовательность B] повторяющиеся.
И ещё вычёркиваем из них те, что встретились в последовательности A
Суммирует оставшие числа из последовательности B.

Формат входного файла
В первой строке входного файла через пробел даны целые числа: NA, seedA1, multiplierA, addendA, divisorA
Во второй строке входного файла через пробел даны целые числа: NB, seedB1, multiplierB, addendB, divisorB

Формат выходного файла
В единственной строке выходного файла вывести сумму.

Пример
test.in
3 2 11 1 107
3 4 11 1 107

test.out
117

Получилось написать такую программу. Она работает только на 1 входные данные. Остальные валятся тестом. Помогите разобраться, пожалуйста. Возможно небольшое вознаграждение.

Код:
program joyli;
type ref = ^node;
node = record
value: int64;
left, right: ref;
end;

const infile = 'test.in';
outfile = 'test.out';

var seed, multiplier, addend, divisor, n: int64;
i, j,k: integer;
fl:text;
atree: ref;

function findnode(root:ref; key:int64):boolean;
var p, parent: ref;
begin
p:=root;
while p<>nil do
 begin
     if key=p^.value then
        begin 
        findnode:=true;
        p^.value:=0;
        exit;
        end;
 parent:=p;
 if key < p^.value then p:=p^.left
 else p:=p^.right;
 end;
findnode:=false;
end;

function newnode(v: int64): ref;
var p: ref;
begin
new(p);
p^.value:=v;
p^.left:=nil;
p^.right:=nil;
newnode:=p;
end;


procedure addnode(var tree: ref; n:int64);
begin if tree=nil then tree:=newnode(n)
else if tree^.value > n then addnode(tree^.left, n)
else addnode(tree^.right, n);
end;

procedure InOrder(root:ref);
     begin
       if root<>nil then
       begin
       InOrder(root^.left);
       K:=k+root^.value;
       InOrder(root^.right);
     end;
   end;

begin 
assign(fl,infile);
reset(fl);
readln(fl);
read(fl, n, seed, multiplier, addend, divisor);

k:=0;
for i:=1 to n do
           begin if not findnode(atree, seed mod 1000000) then
                 begin
                 addnode(atree, seed mod 1000000);
                 seed:=(seed*multiplier+addend) mod divisor;
                 end;
                 end;
           
           reset(fl);
           read(fl, n, seed, multiplier, addend, divisor);
           for i:=1 to n do
           begin
           if findnode(atree, seed mod 1000000) then atree^.value:=0;
                 seed:=(seed*multiplier+addend) mod divisor;
           end;
           
           
inorder(atree);
close(fl);
assign(fl, outfile);
rewrite(fl);
write(fl,k);
close(fl);
end.
Maksik вне форума Ответить с цитированием
Старый 22.06.2010, 21:57   #2
Maksik
Пользователь
 
Регистрация: 24.06.2009
Сообщений: 14
По умолчанию

Задача решена.

Последний раз редактировалось Maksik; 23.06.2010 в 07:54.
Maksik вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Двоичные деревья Raz0r Помощь студентам 7 11.12.2011 10:32
Двоичные деревья (паскаль). patisson74 Помощь студентам 2 16.11.2010 23:46
Двоичные деревья в Паскале Paulo Помощь студентам 0 25.06.2009 23:31
Двоичные деревья. 3 задачки. Срочно rustam29 Фриланс 9 13.06.2009 18:02