Форум программистов, компьютерный форум, киберфорум
Free Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/25: Рейтинг темы: голосов - 25, средняя оценка - 4.56
0 / 0 / 0
Регистрация: 31.08.2014
Сообщений: 35
1

Найти в заданной серии показаний прибора минимальное произведение двух показаний

10.01.2015, 19:31. Просмотров 4694. Ответов 9
Метки нет (Все метки)


Решение:
Pascal
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
program C4_DEMO2015B;
const
    C = 10000000;
var
    nums : array [1..C] of real;
    min_pr : real;
    n, m : integer;
    k : integer;
    pr : real;
    a : pinteger;
begin
    readln(k);
    GetMem(a, k * sizeof(integer)); 
    for n:=0 to k-1 do readln(nums[n]);
    min_pr:=1000*10000+1;
    for n:=1 to (k-6) do
        for m:=(n+6) to k do begin
            pr:=nums[n-1]*nums[m-1];
            if (pr < min_pr) then min_pr:=pr;
            writeln(sizeof(a));
        end;
        
        FreeMem(a);
        writeln(min_pr:8:2);
end.
Собственно, вопрос: В критериях оценивания сказано, что минимальное необходимое количество - шесть(см. ниже), но я не понимаю к чему это "шесть" относится, к кол-ву элементов или, может, кол-во памяти? Правильно ли я решил задачу при поставленных критериях? Заранее спасибо.

На спутнике «Фотон» установлен прибор, предназначенный для измерения энергии космических лучей. Каждую минуту прибор передаёт по каналу связи неотрицательное вещественное число - количество энергии, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний прибора минимальное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Входные данные представлены следующим образом. В первой строке задаётся число N - общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно неотрицательное вещественное число - очередное показание прибора.
Пример входных данных:
11
12
45.3
5.5
4
25
23
21
20
10
12
26
Программа должна вывести одно число - описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 48

Программа правильно работает для любых соответствующих условию входных данных. При этом не используются массивы и другие структуры данных, размер которых зависит от количества входных элементов, а время работы пропорционально этому количеству. Возможно использование массивов и динамических структур данных (например, контейнеры STL в программе на языке C++) при условии, что в них в каждый момент времени хранится фиксированное число элементов, требующих для хранения меньше 1кб (минимально необходимое количество - шесть; допускается решение с запасом).
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.01.2015, 19:31
Ответы с готовыми решениями:

Найти минимальное произведение двух показаний из множества показаний прибора
Здравствуйте. Я попытался решить самую последнюю задачу C3 из ЕГЭ по информатике. Но моя программа...

Найти в серии показаний минимальное произведение двух показаний, между которыми прошло не менее 6 минут
Добрый день, задали по информатике на днях решить следующую задачу: На спутнике «Фотон»...

В компонент Label вывести надпись «произведение показаний» и добавить текущее значение произведения показаний счетчиков
Разместите на форме два компонента Edit и два компонента UpDown. Первый счетчик должен отображать...

Изменение показаний прибора
Прошу у Вас помощи При увеличении сопротивление на втором резисторе, какой из &quot; приборов&quot; изменит...

9
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5693 / 3408 / 2429
Регистрация: 22.11.2013
Сообщений: 9,560
Записей в блоге: 1
11.01.2015, 17:22 2
Лучший ответ Сообщение было отмечено findr как решение

Решение

Цитата Сообщение от findr Посмотреть сообщение
Правильно ли я решил задачу при поставленных критериях?
При этом не используются массивы и другие структуры данных, размер которых зависит от количества входных элементов ...
Цитата Сообщение от findr Посмотреть сообщение
Pascal
1
2
3
4
5
6
7
const
    C=10000000;
var
    nums: array [1..C] of Integer;
...
    readln(k);
    GetMem(a, k * sizeof(integer));
Размер массива a напрямую зависит от количества элементов, следовательно, ваше решение не соответствует требованиям.

Про 6 и "с запасом" -- можно
Pascal
1
2
var
  a: array [1..6] of Integer;
или вместо шести немного больше ("с запасом", 7, 8, ...).

Добавлено через 12 минут
Кроме того, ваша программа неэффективна ни по памяти (см. nums, GetMem(a, k * sizeof(integer)), который, кстати, не используется), ни по времени (см. for n:=1 to (k-6) do for m:=(n+6) to k do ...).

Добавлено через 4 минуты
Указание к решению:
обратите внимание на тот факт, что минимальное произведение дадут два минимальных элемента, отстоящие друг от друга более чем на 6 элементов. Найдите за один проход такую пару, выведите произведение их в качестве результата.
1
0 / 0 / 0
Регистрация: 31.08.2014
Сообщений: 35
12.01.2015, 10:28  [ТС] 3
Цитата Сообщение от bormant Посмотреть сообщение
Указание к решению:
обратите внимание на тот факт, что минимальное произведение дадут два минимальных элемента, отстоящие друг от друга более чем на 6 элементов. Найдите за один проход такую пару, выведите произведение их в качестве результата.
И тогда программа будет эффективна и по времени и по памяти?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5693 / 3408 / 2429
Регистрация: 22.11.2013
Сообщений: 9,560
Записей в блоге: 1
12.01.2015, 11:12 4
Да.
По памяти: для обработки списка потребуется массив на 6 значений плюс одна переменная, либо массив на 7 значений ("с запасом").
По времени: время одного прохода по списку пропорционально количеству элементов списка.
0
0 / 0 / 0
Регистрация: 31.08.2014
Сообщений: 35
12.01.2015, 19:30  [ТС] 5
Цитата Сообщение от bormant Посмотреть сообщение
Да.
По памяти: для обработки списка потребуется массив на 6 значений плюс одна переменная, либо массив на 7 значений ("с запасом").
По времени: время одного прохода по списку пропорционально количеству элементов списка.
Что-то вроде этого?
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
program C4_DEMO2015B;
const
    C = 7;
var
    nums : array [1..C] of real;
    min_pr : real;
    m, t : integer; // счетчики циклов
    N : integer; // всего элементов
begin
    readln(N);
    min_pr:=1000*1000;
    for m:=1 to C do readln(nums[m]);
    if ((min_pr-nums[1]*nums[C]) > 0.01 ) then min_pr:=nums[1]*nums[C]; 
    for t:=1 to (N-C) do begin
        for m:=1 to (C-1) do nums[m]:=nums[m+1];
        readln(nums[C]);
        if (nums[1]*nums[C] < min_pr) then min_pr:=nums[1]*nums[C];
    end;
 
    writeln(min_pr:8:2);
end.
Теперь программа является эффективной по обоим параметрам?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5693 / 3408 / 2429
Регистрация: 22.11.2013
Сообщений: 9,560
Записей в блоге: 1
12.01.2015, 21:06 6
Эффективной -- да, правильной -- нет.
Посмотрите на ряд: 1 2 3 4 5 6 7 6 5 4 3 2 1.
Минимальное произведение: 1*1 = 1.
А у вас?

Вы проверяете только те числа, расстояние между которыми равно ровно 6. Но это условию не соответствует.
А вот если б сначала искали 2 минимальных числа, отстоящих друг от друга на 6 и более элементов, то нашли бы 1 и 1. Перемножив, получили бы 1.

Другой не очень эффективный момент: рассмотрите вместо постоянного сдвига 6 элементов (стр.15) возмжность замены на циклическую очередь. Хотя, для 6 элементов это может быть и лишним, в конце концов, это время на сдвиг по отношению к времени на 1 элемент постоянно, следовательно от N зависит пропорционально, то есть условию в принципе соответствует.
0
0 / 0 / 0
Регистрация: 31.08.2014
Сообщений: 35
13.01.2015, 13:21  [ТС] 7
Цитата Сообщение от bormant Посмотреть сообщение
Вы проверяете только те числа, расстояние между которыми равно ровно 6. Но это условию не соответствует.
А вот если б сначала искали 2 минимальных числа, отстоящих друг от друга на 6 и более элементов, то нашли бы 1 и 1. Перемножив, получили бы 1.
Кажется, получилось
Pascal
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
program C4_DEMO2015B;
const
    C = 6;
var
    min1, min2 : real;
    cnt : integer; //счетчик минут
    i : integer; //счтечик цикла
    num : real;
    N : integer; // всего измерений
begin
    readln(N);
    min1:=1000+1;
    min2:=1000+1;
    for i:=1 to N do begin
        readln(num);
        if num < min1 then begin
            min1:=num;
            cnt:=1;
        end else begin
            if (cnt >= C) and (num < min2) then min2:=num;
            inc(cnt);
        end;
    end;
    writeln(min1*min2:8:2);
end.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5693 / 3408 / 2429
Регистрация: 22.11.2013
Сообщений: 9,560
Записей в блоге: 1
13.01.2015, 15:38 8
Отлично!
Отлично от правильного. Но уже ближе.

7 6 5 4 1 1 2 3

0
Cyborg Drone
13.01.2015, 22:29
  #9

Не по теме:

Тема отредактирована. Отпишитесь в случае неверного редактирования.

0
0 / 0 / 0
Регистрация: 31.08.2014
Сообщений: 35
14.01.2015, 18:28  [ТС] 10
Цитата Сообщение от bormant Посмотреть сообщение
Отлично!
Отлично от правильного. Но уже ближе.
7 6 5 4 1 1 2 3
Pascal
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
program C4_DEMO2015B;
const
    C = 6;
var
    min1, min2 : real;
    cnt : integer; //счетчик минут
    i : integer; //счтечик цикла
    num : real;
    N : integer; // всего измерений
begin
    readln(N);
    min1:=1000+1;
    min2:=1000+1;
    for i:=1 to N do begin
        readln(num);
        if (num < min1) and (N-i >= 6) then begin
            min1:=num;
            cnt:=1;
        end else begin
            if (cnt >= C) and (num < min2) then min2:=num;
            inc(cnt);
        end;
    end;
    writeln(min1*min2:8:2);
end.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.01.2015, 18:28

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Найти характер зависимости показаний вольтметра от положения движка на потенциометре
К потенциометру с сопротивлением 2 кОм, имеющему длину обмотки 20 см, приложено напряжение 400 В....

Разница показаний
Сайт работает с августа, счетчики мейла, лайвинтернета, рамблера тпоказывают всреднем по 20-40 чел...

Снятие показаний с датчиков
Доброе время суток! Интересует вопрос, какими способами можно снимать показания с...

Изменение показаний приборов
Прошу,помогите пожалуйста с заданием(в электротехнике вообще не разбираюсь):рис.8,задание 5.


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

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

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