Моё меню Общее меню Пользователи Правила форума Все прочитано
Вернуться   uForum.uz > ИКТ и телеком > IT-индустрия > Софт > Программирование
Знаете ли Вы, что ...
...до того как открыть новую тему, стоит использовать поиск: такая тема уже может существовать.
<< Предыдущий совет - Случайный совет - Следующий совет >>

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


Ответить

 
Опции темы Опции просмотра
Старый 27.07.2009 23:12   #11  
Real ID Group uParty Member Ultimate
Аватар для Nadir Zaitov
Оффлайн
Сообщений: 13,210
+ 4,958  9,176/3,940
– 170  137/105

UzbekistanОтправить сообщение для Nadir Zaitov с помощью Skype™
Предлагаю перевести спортивное программирование в "Разминку для мозгов " и выкладывать туда интересные задачки и их программировать.
__________________
Тот факт, что медуза выжила 650 миллионов лет без мозгов, даёт надежду многим.
Ответить 
Старый 27.07.2009 23:14   #12  
Pre Open ID Group
Аватар для Khamza Davletov
Оффлайн
Сообщений: 30
+ 34  6/3
– 0  0/0

UzbekistanОтправить сообщение для Khamza Davletov с помощью ICQОтправить сообщение для Khamza Davletov с помощью YahooОтправить сообщение для Khamza Davletov с помощью Skype™
Цитата:
Сообщение от dert Посмотреть сообщение
Khamza Davletov,http://algolist.ru/ очень полезный сайтик. Там можно и книжечки разные найти, да и форум заюзать
Спасибо! Надо будет как небудь по участвовать тоже онлайн. Ато примерно каждые пол года из acm.sgu.ru приходят уведомление об олимпиадax, но ни разу не учавствовал .

Короче тоже покoпался, нашел кое что интересное на английском.

http://rapidshare.com/files/25570747...s-1-4.97802013

http://www.megaupload.com/?d=0DGYFIRZ (Programming Pearls)
Ответить 
Старый 28.07.2009 22:34   #13  
Аватар для Kane
Оффлайн
Сообщений: 373
+ 22  135/75
– 3  7/6

Afghanistan
Глубже Кнута книг не видел. Если нужно быстро и без глубокой теории - Кормен.
Ответить 
Старый 28.07.2009 23:54   #14  
Аватар для YUU
Оффлайн
LLC
Creator
Сообщений: 7,681
+ 2,984  2,763/1,705
– 610  407/288

Uzbekistan
программирование ради программирования - напрасная трата времени и усилий.

Вот если реальную задачу поставить и кто решит тому лавры и призы - то да -смысл есть
Ответить 
Реклама и уведомления
Старый 30.07.2009 17:30   #15  
Pre Open ID Group
Аватар для Khamza Davletov
Оффлайн
Сообщений: 30
+ 34  6/3
– 0  0/0

UzbekistanОтправить сообщение для Khamza Davletov с помощью ICQОтправить сообщение для Khamza Davletov с помощью YahooОтправить сообщение для Khamza Davletov с помощью Skype™
Цитата:
Сообщение от YUU Посмотреть сообщение
программирование ради программирования - напрасная трата времени и усилий.

Вот если реальную задачу поставить и кто решит тому лавры и призы - то да -смысл есть
Только не говорите что вы незнали то, что в interview на работу в Microsoft, Google, IBM... задают типичные вопросы
Ответить 
Старый 30.07.2009 21:27   #16  
Pre Open ID Group
Аватар для Khamza Davletov
Оффлайн
Сообщений: 30
+ 34  6/3
– 0  0/0

UzbekistanОтправить сообщение для Khamza Davletov с помощью ICQОтправить сообщение для Khamza Davletov с помощью YahooОтправить сообщение для Khamza Davletov с помощью Skype™
Реальная задача так реальная задача. Приведу task из одного интервью на одной всеми известной компании

Цитата:
You are given an implementation of a LIFO (Last In First Out) data structure, which is also known as a stack:

class LIFO
{
public:
void push(int n); // push n onto the stack
int isempty(void); // test whether stack is empty
int pop(void); // pop top of stack, can be called iff !isempty()
}

Example call sequence:

LIFO l;
l.push(1); l.push(2); l.push(3);
l.pop(); // returns 3
l.pop(); // returns 2
l.pop(); // returns 1

1. Using this LIFO class (which you do not need to implement), implement a FIFO (First in First Out) data structure, also known as a queue.

2. Explain what the complexity of your algorithm is when a sequence of n subsequent push (or n subsequent pop) operations are performed on the LIFO, and whether this complexity is optimal.

class FIFO
{
private:
LIFO l1;
LIFO l2;
public:
void enqueue(int n); // add n to front of queue
int isempty(void); // test whether queue is empty
int dequeue(void); // remove last element of queue, can be called if !isempty()
}

Example call sequence:

FIFO f;
f.enqueue(1); f.enqueue(2); f.enqueue(3);
f.dequeue(); // returns 1
f.dequeue(); // returns 2
f.dequeue(); // returns 3
Больше всего интересует 2й пункт. Мархамат!

Последний раз редактировалось Khamza Davletov; 30.07.2009 в 21:56.
Ответить 
Старый 30.07.2009 22:51   #17  
Real ID Group
Аватар для Rooslan Khayrov
Оффлайн
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114  374/183
– 6  9/8

Switzerland
Если использовать вот такую реализацию, то при условии, что все операции со стеком выполняются за константное время, любая последовательность из N операций enqueue и dequeue будет выполнена за O(N) время, т.е. амортизированная сложность оптимальна.
Ответить 
"+" от:
Старый 30.07.2009 23:01   #18  
Real ID Group
Аватар для Rooslan Khayrov
Оффлайн
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114  374/183
– 6  9/8

Switzerland
Оффтоп:
Кстати, неалгоритмический вопрос на засыпку. Представьте, что тестируя своё решение, вы написали нечто такое:
Код:
cout << f.dequeue() << endl
     << f.dequeue() << endl
     << f.dequeue() << endl;
Почему это плохая идея?
Ответить 
Старый 31.07.2009 00:38   #19  
Pre Open ID Group
Аватар для Khamza Davletov
Оффлайн
Сообщений: 30
+ 34  6/3
– 0  0/0

UzbekistanОтправить сообщение для Khamza Davletov с помощью ICQОтправить сообщение для Khamza Davletov с помощью YahooОтправить сообщение для Khamza Davletov с помощью Skype™
Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Если использовать вот такую реализацию, то при условии, что все операции со стеком выполняются за константное время, любая последовательность из N операций enqueue и dequeue будет выполнена за O(N) время, т.е. амортизированная сложность оптимальна.
http://dumpz.org/11074 - это есть решение для пункта 1. Но пункт 2 у вас явно не полный .

1. Вот например, http://dumpz.org/11075/ - тоже решение для пункта 1, но оно не оптимальнее чем ваш. Почему? - Хотя даже видно почему, но надо доказать уже математическим путём.

2. Ну это тоже не делает ваш алгоритм самым оптимальным. Нужно доказать что оптимальнее нельзя .

P.S. И то, что "Big O" равен O(n) не плохо было бы обосновать математическим путём.

Последний раз редактировалось Khamza Davletov; 31.07.2009 в 00:42.
Ответить 
Ответить
Опции темы
Опции просмотра




Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Advertisement System V2.5 By Branden
OOO «Единый интегратор UZINFOCOM»


Новые 24 часа Кто на форуме Новички Поиск Кабинет Все прочитано Вверх