9 задачек на программирование .помогите разобраться
Задание 3. Предложите наиболее быстрый алгоритм сортировки массива, элементами которого являются числа от одного до ста.сортировка-подсчетом
Ответ:
Заранее спасибо за потраченное вами время на прочтение этой ересиЭто реальне ересь, зачем ты это выложил? Тебе помощь нужна?
В первом наверняка имеется в виду STL'ный deque (это судя по уровню остальных вопросов).
>> быстро добавлять и удялять элементы, обращаться по индексу
> B-дерево
Не обязательно, бывают и другие деревья с той же асимптотикой.
И не только деревья.
>> Рассмотрим библиотечную функцию qsort
Это не зависит от того, использовал ты её или нет, знать должен.
На упорядоченных.
>> Предложите наиболее быстрый алгоритм сортировки массива,
>> элементами которого являются числа от одного до ста.
> первое, что приходит в голову это алгоритм быстрой сортировки Хоара
"Первый ответ студента всегда неверен." В таких случаях сортируют подсчётом.
>> Какие проблемы вы видите в приведенной ниже программе?
> проблемы в корявом выводе результатов
Проблемы в знаках "C", "++" и их комбинации.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
> B-дерево
Не обязательно, бывают и другие деревья с той же асимптотикой.
И не только деревья.
>> Рассмотрим библиотечную функцию qsort
Это не зависит от того, использовал ты её или нет, знать должен.
На упорядоченных.
>> Предложите наиболее быстрый алгоритм сортировки массива,
>> элементами которого являются числа от одного до ста.
> первое, что приходит в голову это алгоритм быстрой сортировки Хоара
"Первый ответ студента всегда неверен." В таких случаях сортируют подсчётом.
>> Какие проблемы вы видите в приведенной ниже программе?
> проблемы в корявом выводе результатов
Проблемы в знаках "C", "++" и их комбинации.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Проблемы в знаках "C", "++" и их комбинации.Это вообще не в тему. Так на любое можно ответить: проблема в знании "++".
Да и вообще проблема к "++" имеет очень посредственное отношение.
Заранее спасибо за потраченное вами время на прочтение этой ересиможет комуто покажется ,что это ересь...а так оочень сильно помощь нужна!
Это реальне ересь, зачем ты это выложил? Тебе помощь нужна?
Ну так разбирайся. Это явно не в универе спросили. Думаешь тебя не раскусят, когда ты принесешь ответы?
Задание 9.Пиши merge. Будет полезно.
Ну так разбирайся. Это явно не в универе спросили. Думаешь тебя не раскусят, когда ты принесешь ответы?мне бы просто понять правильно ли я ответил на эти вопросы.
в процессе буду выкладывать ответы на эти вопросы
мне бы просто понять правильно ли я ответил на эти вопросы.ответы ты дал только на три. Два из них были неправильными. В "ответах" на остальные прослеживается нежелание самому подумать.
Поставившие минусы могут спросить, попытаюсь объяснить то, что они не поняли 
1) либо хэш, либо красно-черные деревья.
7) по порядку:
— не подключен stdio.h
— функция возвращает ссылку на локальную переменную
— далее эту ссылку (т.е. указатель) распечатывают как целое число
— функция main объявлена как int, но ничего не возвращает.
7) по порядку:
— не подключен stdio.h
— функция возвращает ссылку на локальную переменную
— далее эту ссылку (т.е. указатель) распечатывают как целое число
— функция main объявлена как int, но ничего не возвращает.
1) гонишь ты. Это ты пишешь не доступ по индексу, а доступ по ключу, там это лишнее. Заметь, я еще выше написал ответ, который с вероятностью 90% там ожидали.
2) тут все верно. Не подключен stdio.h — лол, зачет.
2) тут все верно. Не подключен stdio.h — лол, зачет.
На 1-3 ответы уже дали.
4. Я так понимаю, книжка по C++ пролистана по диагонали и слово protected ты там не заметил, а о наследовании вообще не слышал?
5. В map'е пары ключ-значение хранятся в сбалансированном дереве, сложность поиска в котором логарифмическая по количеству элементов.
По определению алгоритма find, он возвращает такой итератор i, что *i = value. Вот только map:
:operator * возвращает пару, так что выражение find(m.begin m.end 5) не верно (на gcc не проверял, но cl выдал кучу ошибок выведения типа для оператора сравнения.
6. судя по ответу, либо мозги не используются, либо знания напрочь отсутствуют. Только без обид: для решения примера прочитать про операторы new, delete, new[] и delete[] и немного подумать более чем достаточно. Инструментальными средствами имеет смысл пользоваться если такие элементарные примеры умеешь решать, в противном случае они тебе не помогут.
Правильный ответ - при n=2 и n=0. В остальных случаях будет аварийное завершение при попытке выделения памяти (n<0 либо исключение до выделения (n=1 либо освобождение (n>2 хоть и некорректное. Впрочем, подозреваю, что можно реализовать операторы new[] и delete[] так, что освобождение выделенного по new[] с помощью delete приведёт к утечке (например, выделять два куска памяти, в одном из которых будет инфа о количестве элементов массива либо ошибке (указатель будет сдвигаться).
7 - ответили.
8. не написано using namespace std; и соответствующие инклуды; кроме того, никто не обещал, что после push_back адрес нулевого элемента не изменится, так что в данном случае следует хранить элементы по значению, либо получать их в последней строчке.
4. Я так понимаю, книжка по C++ пролистана по диагонали и слово protected ты там не заметил, а о наследовании вообще не слышал?
5. В map'е пары ключ-значение хранятся в сбалансированном дереве, сложность поиска в котором логарифмическая по количеству элементов.
По определению алгоритма find, он возвращает такой итератор i, что *i = value. Вот только map:
:operator * возвращает пару, так что выражение find(m.begin m.end 5) не верно (на gcc не проверял, но cl выдал кучу ошибок выведения типа для оператора сравнения.6. судя по ответу, либо мозги не используются, либо знания напрочь отсутствуют. Только без обид: для решения примера прочитать про операторы new, delete, new[] и delete[] и немного подумать более чем достаточно. Инструментальными средствами имеет смысл пользоваться если такие элементарные примеры умеешь решать, в противном случае они тебе не помогут.
Правильный ответ - при n=2 и n=0. В остальных случаях будет аварийное завершение при попытке выделения памяти (n<0 либо исключение до выделения (n=1 либо освобождение (n>2 хоть и некорректное. Впрочем, подозреваю, что можно реализовать операторы new[] и delete[] так, что освобождение выделенного по new[] с помощью delete приведёт к утечке (например, выделять два куска памяти, в одном из которых будет инфа о количестве элементов массива либо ошибке (указатель будет сдвигаться).
7 - ответили.
8. не написано using namespace std; и соответствующие инклуды; кроме того, никто не обещал, что после push_back адрес нулевого элемента не изменится, так что в данном случае следует хранить элементы по значению, либо получать их в последней строчке.
(это судя по уровню остальных вопросов)мне тут сообщили, что это вопросы из Яндекса
мне тут сообщили, что это вопросы из ЯндексаНичто не мешает им задать простые вопросы.
CBoss что ли?
забей хуй сразу на это.
забей хуй сразу на это.
— далее эту ссылку (т.е. указатель) распечатывают как целое числоЭ-э-э... Правда?
Т.е.
int a=5;
int &b=a;
printf("%d=%d",a,b);
выдаст не '5=5'?
6 не тестить надо, а по определению смотреть, + тут new[n] - надо освобождать delete[] + еще я не помню что там стандарт говорит о new[0]
7 не в корявом выводе результатов, это следствие, причем следствие проблемы(про которую спрашивают) и множества факторов окружения, от которых программы зависеть по идее не должны (проблема в возврате ссылки на лок переменную). кстати, окружение может быть и таким , что проблема не будет провляться и все будет работать, типа (это к вопросу "ща на студии потесчу" )
8 проблема в том , что ссылка на нулевой элемент будет валидной до первого вызова метода, который может вызвать внутреннее переаллоцирование массива, в данном случае второй push_back. Обрати внимание на "может" - в данном случае обыно все будет работать ок (т.к. вряд ли массив сначала выделит память только для одного элемента) но если так писать, то это приводит к тому, что "при разработке и тестировании все работает, а у самого главного клиента все падает" (на это дело есть какая-то умная терминология, типа метода, когда итераторы инвалидируются, время жизни итераторов или что-то в этом роде, в книжках по STL такое должно быть описано)
7 не в корявом выводе результатов, это следствие, причем следствие проблемы(про которую спрашивают) и множества факторов окружения, от которых программы зависеть по идее не должны (проблема в возврате ссылки на лок переменную). кстати, окружение может быть и таким , что проблема не будет провляться и все будет работать, типа (это к вопросу "ща на студии потесчу" )
8 проблема в том , что ссылка на нулевой элемент будет валидной до первого вызова метода, который может вызвать внутреннее переаллоцирование массива, в данном случае второй push_back. Обрати внимание на "может" - в данном случае обыно все будет работать ок (т.к. вряд ли массив сначала выделит память только для одного элемента) но если так писать, то это приводит к тому, что "при разработке и тестировании все работает, а у самого главного клиента все падает" (на это дело есть какая-то умная терминология, типа метода, когда итераторы инвалидируются, время жизни итераторов или что-то в этом роде, в книжках по STL такое должно быть описано)
7 не в корявом выводе результатов, это следствие, причем следствие проблемы(про которую спрашивают) и множества факторов окружения, от которых программы зависеть по идее не должны (проблема в возврате ссылки на лок переменную). кстати, окружение может быть и таким , что проблема не будет провляться и все будет работать, типа (это к вопросу "ща на студии потесчу" )Окружение? Т.е. в гну будет работать, а в бзде (хз как у них там это называется) — нет? Или от переменных окружения? Ты вообще слова в словаре смотри =)
—
Day of week, bitch, environment!
Когда я читал мне показалось, что он имел в виду, что ошибка в том, что возвращается ссылка на локальную переменную И используется потом.
молодец, доебался до слова, если бы топикстартер еще не врубился, что я имею в виду, то это еще ладно...
7 не в корявом выводе результатов, это следствие, причем следствие проблемы(про которую спрашивают) и множества факторов окружения, от которых программы зависеть по идее не должны (проблема в возврате ссылки на лок переменную). кстати, окружение может быть и таким , что проблема не будет провляться и все будет работать, типа (это к вопросу "ща на студии потесчу" )
Окружение? Т.е. в гну будет работать, а в бзде (хз как у них там это называется) — нет? Или от переменных окружения? Ты вообще слова в словаре смотри =)
я имел в виду что это прежде всего зависит от компилятора(как он лок перем положит, начнет ли и как оптимизить соглашений о вызове функций (которые прежде всего зависят от архитетуры и пр от кода (если использование пойдет не сразу за вызовом а после вызова др функции, то почти наверное мусор получится мб еще от чего. Может че-то я лишнего написал.
зы посмотри сам=) значение слова окружение, напрмер, на грамоте.ру 4-ое значение
Когда я читал мне показалось, что он имел в виду, что ошибка в том, что возвращается ссылка на локальную переменную И используется потом.С этим не спорю. Но там был второй пункт: "ссылка (ТО ЕСТЬ УКАЗАТЕЛЬ) выводится как целое число", который и вызвал мое удивление.
8 проблема в том , что ссылка на нулевой элемент будет валидной до первого вызова метода, который может вызвать внутреннее переаллоцирование массива, в данном случае второй push_back. Обрати внимание на "может" - в данном случае обыно все будет работать ок (т.к. вряд ли массив сначала выделит память только для одного элемента) но если так писать, то это приводит к тому, что "при разработке и тестировании все работает, а у самого главного клиента все падает" (на это дело есть какая-то умная терминология, типа метода, когда итераторы инвалидируются, время жизни итераторов или что-то в этом роде, в книжках по STL такое должно быть описано)Например, std::string в реализации stl идущей с мелкософтным компилятором, работает так: очень мелкие строки хранит внутри себя (используя, вроде, в том числе поля выделенные под указатель на память для более крупных строк а для больших строк уже выделяется память. Вполне может быть что у vector'а подобное поведение. В любом случае, выделенное утверждение можно писать уже после проверки на популярных компиляторах. И, как минимум, на cl оно такой проверки не выдержит.
еще я не помню что там стандарт говорит о new[0]хз по стандарту это или нет, но afaik, как правило, память всё равно выделится.
Я тебя понял, просто при первом прочтении не обратил внимание.
Оставить комментарий
gukochka
Задание 1. Какую структуру данных вы выберете, если нужно быстро добавлять и удялять элементы, обращаться по индексу?Ответ:
B-дерево?
Задание 2. Рассмотрим библиотечную функцию qsort(...) для сортировки элементов массива. Определите, на каких входных данных эта функция будет работать максимально долго.
Ответ:
я хз ,ни разу не юзал эту функцию...
Задание 3. Предложите наиболее быстрый алгоритм сортировки массива, элементами которого являются числа от одного до ста.
Ответ:
первое ,что приходит в голову это алгоритм быстрой сортировки Хоара( быстрая сортировка но этот выбор равносилен выстрелам из пушки по воробьям.Может есть другие способы решения данной задачки ,аналогичные по скорости?
Задание 4. Определите, какие поля доступны из метода Foo?
class A { int a; public: int b; protected: int c; };
struct B { int a; private: int b; };
class C: public A {
void Foo {
A a; B b; // ...
}
};
Ответ:
поле b из класса А,поле а из класса В
Задание 5. Рассмотрим ассоциативный массив map<int, int > m из n элементов. Оцените время работы функции m.find(5) и find(m.begin m.end 5). Сравните полученные результаты.
Ответ:
Задание 6. При каких значениях n в функции Foo(n) будут возникать утечки памяти?
int* Bar(int n) {
if (n == 1)
throw "exception";
return new int[n];
}
void Foo(int n) {
int *a = Bar(n);
if (n <= 2) return;
delete a;
}
Ответ:будем тестить на вижуал студио
Задание 7. Какие проблемы вы видите в приведенной ниже программе?
int& Square(int n) {
int k = n * n;
return k;
}
int main {
for (int i = 0; i < 10; i++)
printf("%d^2 = %d\n", i, Square(i;
}
Ответ: проблемы в корявом выводе результатов
Задание 8. Опишите, какие проблемы вы видете в приведенном ниже фрагменте?
int Foo {
vector<int> xs;
xs.push_back(1);
int &x0 = xs[0];
xs.push_back(2);
int &x1 = xs[1];
return x0+x1;
}
Ответ:
Задание 9. Напишите программу, реализующую внешнюю сортировку. Оцените время работы и количество операций записи на диск в зависимости от размера исходного файла и оперативной памяти.
Ответ : в процессе
Заранее спасибо за потраченное вами время на прочтение этой ереси