инф. Обработка данных, вводимых из файла в виде последовательности чисел

• Название: Обработка данных, вводимых из файла в виде последовательности чисел
• Дата: 06.12.2021
• Размер: 0.56 Mb.
• Имя файла: ege27_old.doc
• Тип: Документы; #293908
• страница: 1 из 11

© К. Поляков, 2009-2021

27 (высокий уровень, время – 35 мин)

Тема: Обработка данных, вводимых из файла в виде последовательности чисел.

Что проверяется:

Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей.

1.6.3. Построение алгоритмов и практические вычисления.

1.1.3. Строить информационные модели объектов, систем и процессов в виде алгоритмов.

Что нужно знать:

• 
  
  

Материалы от Alex Danov:

• 
  Базовые алгоритмы для решения задач ЕГЭ на программирование: https://www.youtube.com/playlist?list=PLXZ932--vmI_-BWxVtEdU-p-_BtnYfR8p
  
• 
  Решения задач из этого сборника: https://github.com/AlexDanov/InfEGE-27-PascalABC
  
• 
  Разборы задач 27 из этого сборника: https://www.youtube.com/playlist?list=PLXZ932--vmI_ivq9QOC_gpZ2czSe2CLTU
  

Пример задания:

Р-00(Демо-2021). Имеется набор данных, состоящий из пар положительных целых чисел.

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

сумму, соответствующую условиям задачи.

Входные данные

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

6

1 3

5 12

6 9

5 4

3 3

1 1

Для указанных входных данных значением искомой суммы должно быть число 32.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Решение:

1. 
   вспомним (или научимся), как прочитать данные из файла; сначала нужно открыть файл (сделать активным), затем прочитать данные, и затем его закрыть (освободить);
   
2. 
   в языке Python это выглядит так:
   

Fin = open( "27.txt" )

N = int( Fin.readline() )

for i in range(N):

a, b = map( int, Fin.readline().split() )

... # здесь работаем с переменными a и b

Fin.close()

3. 
   в программе на языке PascalABC.NET достаточно просто переключить поток ввода на файл, и после этого читать из него данные так же, как с клавиатуры:
   

var N, i, a, b: integer;

begin

Assign( input, '27.txt' );

Readln( N );

for i:=1 to N do begin

Readln( a, b );

... // здесь работаем с переменными a и b

end;

...

end.

4. 
   в программе на C++ используем файловые потоки из библиотеки fstream:
   

#include

using namespace std;

int main() {

ifstream Fin( "27.txt" );

int N, a, b;

Fin >> N;

for( int i = 0; i < N; i++ ) {

Fin >> a >> b;

... // здесь работаем с переменными a и b

}

...

}

5. 
   пока забудем про требование «чтобы сумма всех выбранных чисел не делилась на 3» и найдём просто максимальную сумму; для этого достаточно выбрать из каждой пары максимальное число:
   

Python:

s = 0

for i in range(N):

a, b = map( int, Fin.readline().split() )

s += max( a, b )

print( s )

PascalABC.NET:

var s := 0;

for i:=1 to N do begin

Readln( a, b );

s += Max(a,b);

end;

Writeln( s )

C++:

int s = 0;

for( int i = 0; i < N; i++ ) {

Fin >> a >> b;

s += max( a, b );

}

cout << s;

6. 
   если полученная сумма не делится на 3, то всё хорошо, а если делится? в этом случае нужно заменить число в одной из пар, вместо максимального взять второе, минимальное;
   
7. 
   при этом для того чтобы сумма получилась максимальной нужно выбрать пару, в которой разница между числами минимальная и не делится на 3 (иначе делимость новой суммы на 3 сохранится)
   
8. 
   будем искать значение dMin – минимальную разницу между числами одной из пар, не делящаяся на 3; тогда при выводе в случае делимости суммы s на 3 выводим s-dMin, что соответствует замене числа в одной паре:
   

Python:

dMin = 10001

for i in range(N):

a, b = map( int, Fin.readline().split() )

s += max( a, b )

d = abs( a-b )

if d % 3 > 0:

dMin = min( d, dMin )

if s % 3 != 0:

print( s )

else:

print( s-dMin )

PascalABC.NET:

var dMin := MaxInt;

for i:=1 to N do begin

Readln( a, b );

s += Max(a,b);

var d := Abs(a-b);

if d mod 3 <> 0 then

dMin := Min( d, dMin )

end;

if s mod 3 <> 0 then

Writeln( s )

else Writeln( s-dMin );

C++:

int dMin = 10001;

for( int i = 0; i < N; i++ ) {

Fin >> a >> b;

s += max( a, b );

int d = abs( a-b );

if( d % 3 > 0 )

dMin = min( d, dMin );

}

if( s % 3 != 0 )

cout << s;

else

cout << s-dMin;

9. 
   приведём полное решение:
   

Python:

Fin = open( "27.txt" )

N = int( Fin.readline() )

s, dMin = 0, 10001

for i in range(N):

a, b = map( int, Fin.readline().split() )

s += max( a, b )

d = abs( a-b )

if d % 3 > 0:

dMin = min( d, dMin )

if s % 3 != 0:

print( s )

else:

print( s-dMin )

PascalABC.NET:

var N, i, a, b : integer;

begin

Assign( input, '27.txt' );

Readln( N );

var s := 0;

var dMin := MaxInt;

for i:=1 to N do begin

Readln( a, b );

s += Max(a,b);

var d := Abs(a-b);

if d mod 3 <> 0 then

dMin := Min(d, dMin)

end;

if s mod 3 <> 0 then

Writeln( s )

else Writeln( s-dMin );

end.

C++:

#include

#include

#include

using namespace std;

int main() {

ifstream Fin( "27-b.txt" );

int N, s = 0, dMin = 10001;

Fin >> N;

for( int i = 0; i < N; i++ ) {

int a, b;

Fin >> a >> b;

s += max( a, b );

int d = abs( a-b );

if( d % 3 > 0 )

dMin = min( d, dMin );

}

if( s % 3 != 0 )

cout << s;

else

cout << s-dMin;

}

10. 
    обработка файла А даёт ответ 127127, а обработка файла B – ответ 399762080
    
11. 
    Ответ: 127127 399762080.
    

Решение (электронные таблицы, И.В. Степанов):

1. 
   загружаем текст в Excel с помощью вкладки Данные/Из текста (используем разделитель - пробел); удаляем первую строку где только одно число (количество)
   

2. 
   В столбце C находим максимальное из каждой пары чисел: вставляем в C1 формулу =МАКС(A1:B1) и копируем ее вниз (двойной щелчок на маркере заполнения)
   

3. 
   вычисляем сумму чисел в столбце C:
   

4. 
   проверяем кратность 3: находим остаток от деления на 3 по формуле =ОСТАТ(C21;3)
   

5. 
   если остаток не равен 0, то искомое число найдено; иначе продолжаем…
   
6. 
   в столбце D для каждой пары находим модуль разности по формуле вида =ABS(A1-B1);
   
7. 
   поскольку нам нужны только пары, в которых разность не делится на 3, записываем 0 в те строчки, где это условие не выполняется; для этого используем условие:
   

=ЕСЛИ(ОСТАТ(A1-B1;3)=0;0;ABS(A1-B1))

8. 
   сортируем диапазон по столбцу D по возрастанию и берем из него первое ненулевое число (минимальную разницу в паре)
   

9. 
   вычитаем его из суммы, полученной ранее:
   

10. 
    можно заполнить столбец E формулами вида =$C$21-D1, тогда результат будет выведен сразу справа от минимальной разности
    

11. 
    Для варианта A получаем 127127, для варианта B - 399762080.
    
12. 
    Ответ: 127127 399762080.