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

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

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

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

22.11.2012, 22:31. Просмотров 276. Ответов 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 );
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.11.2012, 22:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос задача "оценить сортировку" (C++):

В массиве структур студент с полями "ИМЯ" "ВОЗРАСТ" "УСПЕВАЕМОСТЬ" выполнить сортировку по успеваемости по возрастанию - C++
в массиве структур студент с полями "ИМЯ" "ВОЗРАСТ" "УСПЕВАЕМОСТЬ" выполнить сортировку по успеваемости по возрастанию. Использовать...

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

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

3
valeriikozlov
Эксперт С++
4670 / 2496 / 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 );
0
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
23.11.2012, 16:30  [ТС] #3
Что-то не то, посмотрите последний тест.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.11.2012, 17:58 #4
ссылку на задачу можете дать?
0
23.11.2012, 17:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.11.2012, 17:58
Привет! Вот еще темы с ответами:

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс "вентилятор" содержащий в себе классы:...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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