Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
#1

задача "оценить сортировку" - C++

22.11.2012, 22:31. Просмотров 263. Ответов 3
Метки нет (Все метки)

Пусть некотoрая сортирoвка рабoтает ровно c · n · log(n) нанoсекунд для сортировки маccива n чисел. Здесь log(n) обозначает логарифм по оcнoванию 2. Задано макcимальное время работы t, найдите такое наибольшее вещественозначное n, что алгоритм проработает не больше t.


Входные данные
В единственной строке заданы целые числа c, t (1 ≤ c ≤ 100, 1 ≤ t ≤ 2000000000).


Выходные данные
Выведите искомое значение вещественное значение n. Выводите ответ не менее чем с 9 знаками.


Пример(ы)
input.txt
1 8
output.txt
4.00000000000


input.txt
2 16
output.txt
4.00000000000

input.txt
37 12392342
output.txt
23104.999312341137

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long double mid, c, t, l, r, gg = log(2.0);
    cin >> c >> t;
 
    l = 0; 
    r = 99999999/c;
    t /= c;
 
    while(r - l > 0.000000001)
    {
        mid = (l + r)/2.0;
        if(mid*(log(mid)/gg) >= t)
            r = mid;
        else
            l = mid;
 
    }
 
    printf("%.9lf", (l + r)/2.0 );
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.11.2012, 22:31     задача "оценить сортировку"
Посмотрите здесь:

в чем ошибка? задача на "сортировку массива" - C++
Подскажите в чем ошибка в коде. Я должен отсортировать массив по убыванию элементов. #include <iostream> #include <conio.h> ...

Реализовать сортировку массива структур типа "Сотрудник" по убыванию стажа - C++
Здравствуйте, уважаемые форумчане! Задача: Информация о сотрудниках предприятия содержит ФИО, номер отдела, должность, дату начала...

Переделать рекурсивную сортировку "пузырьком" на итеративную - C++
Нужно код переделать сортировку Пузырьком переделать рекурсувную на сортировку циклами. { if(i<=0) return; ...

Нужно в пункт просмотра добавить еще одну "ветку" которая будет отвечать за сортировку - C++
#include <iostream> #include <string.h> using namespace std; class myclass { public: char fio; char nom; char data; ...

Как понять "пузырьковую" сортировку? - C++
Здравствуйте , в книге по теме "массивы" в пример была дана программа "пузырьковой" сортировки массивов: int main() { int nums; ...

задача по С++ "Мастям игральных карт условно присвоены следующие порядковые номера" - C++
Мастям игральных карт условно присвоены следующие порядковые номера:пики-1, трефы-2 , бубны-3, червы-4. Достоинству карт присвоены...

Задача со строками (вывести слово, которое содержит ровно три буквы "и") - C++
Здравствуйте, помогите решить задачу. Пользователь вводит предложение с пробелами, запятыми и тп. Нужно вывести слово, которое...

Задача про файлы и "вагоны" битов - C++
Надо срочно решить другану задачу, а я в C++ вообще мёртвый. Будьте добры, помогите! В общем, такая задача: На вход подается файл, в...

Задача по теме "Кондитерские изделия", классы - C++
Я просто долгое время болел и пропустил тему связанную с классами, а завтра уже надо сдать готовую программу, ребят, помогите...

Динамическое программирование, задача "Уменьшение числа" - C++
Имеется натуральное число N (1 <= N <= 106). За один ход с ним можно произвести следующие действия: Вычесть единицу Разделить на два ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.11.2012, 00:23     задача "оценить сортировку" #2
Попробуйте так сдать:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    long double mid, c, t, l, r, gg = log(2.0), x;
    cin >> c >> t;
 
    l = 0; 
    r = 99999999/c;
    t /= c;
 
    while(r - l > 0.001)
    {
        mid = (l + r)/2.0;
        if(mid*(log(mid)/gg) >= t)
            r = mid;
        else
            l = mid;
 
    }
    x=(int)r;
    r=r-(int)r;
    l=l-(int)l;
    while(r - l > 0.000000001)
    {
        mid = (l + r)/2.0;
        if((mid+x)*(log(mid+x)/gg) >= t)
            r = mid;
        else
            l = mid;
 
    } 
    printf("%.9lf", (l + r+x)/2.0 );
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
23.11.2012, 16:30  [ТС]     задача "оценить сортировку" #3
Что-то не то, посмотрите последний тест.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.11.2012, 17:58     задача "оценить сортировку" #4
ссылку на задачу можете дать?
Yandex
Объявления
23.11.2012, 17:58     задача "оценить сортировку"
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru