К.Ю. Поляков вебинар для учителей информатики г. Сочи 24 марта 2021 года
2 ( Демо-2021 ) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
3 Пишем решение «в лоб». Если получили ответ, то СТОП. Оптимизируем. Переходим к шагу 2. Не нужно оптимизировать без необходимости! !
4 ## var startN:= 174457 ; var endN:= 174505 ; for var x:= startN to endN do begin var count:= 0 ; var divs:= | 0, 0 |; for var d:= 2 to x- 1 do if x. Divs (d) then begin count += 1 ; if count > 2 then break ; divs[count -1 ]:= d; end ; if count = 2 then P rintln ( divs[ 0 ], divs[ 1 ] ); end ; var startN:= 174457 000 ; var endN:= 1745 05 000 ; Как у c корить? ?
5 for var d:= 2 to x div 2 do begin ... end ; Сложность алгоритма не меняется! O ( N 2 ) ! Делители в парах: Проблема: вещественное ! ! Проблема: полные квадраты! ! один делитель
6 ## var x := 100000000000 ; while x < 1000000000000 do begin var sqrtX := sqrt (x); if x <> sqrtX*sqrtX then P rintln (x, x-sqrtX*sqrtX); x := x + 1 ; end ; Ошибка ± 1,53 10 –5 ! ! trunc ? round ? ceil ? ?
7 for var d:= 2 to round( sqrt ( x )) do begin ... end ; 1) полный квадрат 5 round 2) два множителя с разностью 1 5 round round здесь округлит к меньшему! ! round ( sqrt ( x ))
8 var d:= 2 ; while d*d <= x do begin ... d += 1 ; end ; Без вещественных чисел:
9 ## var startN := 174457 ; var endN := 174505 ; for var x:= startN to endN do begin var divs:= new List< integer >; for var d:= 2 to round ( sqrt (x)) do if x. Divs (d) then begin divs.Add(d); if d <> x div d then divs. Add (x div d); if divs.Count > 2 then break ; end ; if divs. Count = 2 then P rintln ( divs[ 0 ], divs[ 1 ] ); end ; var divs:= new List< integer >; divs.Add(d); divs. Count divs. Count d*d <> x
10 function IsPrime (x: integer ): boolean ; begin Result:= False ; if x <= 1 then Exit ; var d:= 2 ; while d*d <= x do begin if x. Divs (d) then Exit ; d += 1 ; end ; Result:= True ; end ;
11 var primes := new List< integer >; for var i:= 1 to 1000000 do if IsPrime (i) then primes. Add (i); P rint ( primes. Count ); Время 0,3 с! !
12 ( Б.С. Михлин ) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [194441; 196500] простые числа, оканчивающиеся на 93.
13 var startN := 194441 ; var endN := 196500 ; for var x:=startN to endN do if (x mod 100 = 93 ) and IsPrime (x) then Println (x);
14 var startN:= 194493 ; var endN:= 196500 ; var x:= startN; while x <= endN do begin if IsPrime (x) then Println (x); x += 100; end ; 194493 x += 100 ; первое, которое оканчивается на 93
15 Рассматриваются целые числа, принадлежащих числовому отрезку [631632; 684934], которые представляют собой произведение двух различных простых делителей. Найдите такое из этих чисел, у которого два простых делителя больше всего отличаются друг от друга.
16 var startN := 631632 ; var endN := 684934 ; var maxDiff := 0 ; var xMaxDiff := 0 ; for var x:=startN to endN do for var d:= 2 to round ( sqrt ( x ))- 1 do if x. Divs (d) and IsPrime (d) and IsPrime (x div d) and (x div d - d > maxDiff ) then begin maxDiff := x div d - d; xMaxDiff := x; end ; Println ( xMaxDiff, maxDiff ); var startN:= 63163200 ; var endN:= 68493400 ; Как у c корить? ?
17 for var x:=startN to endN do for var d:= 2 to round ( sqrt ( x ))- 1 do if x. Divs (d) then begin if IsPrime (x div d) and (x div d - d > maxDiff ) then begin maxDiff := x div d - d; xMaxDiff := x; end ; break; end ; break ; if x. Divs (d) then begin Пара « наименьший-наибольший » имеет наибольшую разность! ! IsPrime (d) первый d всегда простой!
18 var primes := new List< integer >; for var i:= 1 to round ( sqrt (endN)) do if IsPrime (i) then primes. Add (i); Список возможных меньших простых делителей:
19 for var x:= startN to endN do foreach var d in primes do i f x. Divs (d) then begin if IsPrime (x div d) and (x div d - d > maxDiff ) then begin maxDiff := x div d - d; xMaxDiff := x; end ; break ; end ; foreach var d in primes do var startN:= 63163200 ; var endN:= 68493400 ; 16,7 с! !
20 Назовём натуральное число подходящим, если ровно два из его делителей входят в список (7, 11, 13, 19). Найдите все подходящие числа, принадлежащих отрезку [20 000; 30 000] В ответе запишите два целых числа: сначала количество, затем среднее арифметическое всех найденных чисел (только целую часть). Проблемы : ровно два из его делителей входят в список среднее арифметическое всех найденных чисел (сумма может быть очень велика!)
21 var startN := 20000 ; var endN := 30000 ; var count := 0 ; for var x:= startN to endN do begin var divs := | integer (x mod 7 = 0 ), ord (x mod 11 = 0 ), ord (x.Divs( 13 )), 1 - sign (x mod 19 ) |; if divs. Sum = 2 then count += 1 ; end ; Println ( count ); Как быть с суммой? ? int64 double var divs := | integer (x mod 7 = 0 ), ord (x mod 11 = 0 ), ord (x.Divs( 13 )), 1 - sign (x mod 19 ) |; можно по-разному!
22 (Статград) Найдите все натуральные числа, принадлежащие отрезку [289123456; 389123456] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Проблемы : долго считает…
23 var startN := 289123456 ; var endN := 389123456 ; for var x:=startN to endN do begin var divs := new List< integer >; for var d:= 2 to x- 1 do if x. Divs ( d ) then divs. Add (d); if divs. Count = 3 then Println ( x ); end ; Как у c корить? ?
24 var startN := 289123456 ; var endN := 389123456 ; for var sqrtX:=trunc(sqrt(startN)) to ceil(sqrt(endN)) do begin var x := sqrtX*sqrtX; var divs := new List< integer >; for var d:= 2 to x- 1 do if x. Divs ( d ) then divs. Add (d); if divs. Count = 3 then Println ( x ); end ; Как у c корить? ? Три (нечётное число) нетривиальных делителя – полный квадрат! for var sqrtX:= trunc ( sqrt (startN)) to ceil ( sqrt (endN)) do begin var x := sqrtX*sqrtX;
25 Любое число единственным способом представляется в виде произведения простых чисел: Число нетривиальных делителей: Если = 3 :
26 var startN := 289123456 ; var endN := 389123456 ; for var qX:= trunc ( sqrt ( sqrt (startN))) to ceil ( sqrt ( sqrt (endN))) do begin if I sPrime (qX) then Println ( qX*qX*qX*qX ); end ; 0,016 с! !
27 ( Демо-2021 ) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
28 ## uses school; for var x:= 174457 to 174505 do begin var divs := x.Divizors ; if divs. Count = 4 then Println ( divs [ 1 ], divs [ 2 ] ); end ; x. Divizors ;
29 ## uses school ; ( 174457..174505 ) . Select ( x->x. Divizors ) . Where ( x->x. Count = 4 ) . Select ( x->(x[ 1 ],x[ 2 ]) ) . Print Lines ; ( 174457..174505 ) последовательность чисел Презентации С.С. Михалковича: http://www.pascalabc.net/downloads/Presentations/Tutorials/Sequences.pdf http://www.pascalabc.net/downloads/Presentations/Tutorials/ProcFuncLambdas.pdf
30 function mySeq ( a, b: integer ): sequence of integer ; begin while a <= b do begin yield a; a += 1 ; end ; end ; begin foreach var x in mySeq ( 10, 20 ) do Print (x); end. sequence of integer yield a; 10 11 12 13 14 15 16 17 18 19 20
31 ( 10..20 ). Select ( x->x. Divizors ). PrintLines ; заменить каждый элемент последовательности на список его делителей [1,2,5,10] [1,11] [1,2,3,4,6,12] [1,13] [1,2,7,14] [1,3,5,15] [1,2,4,8,16] [1,17] .. все делители 10 11 12 13
32 ( 10..20 ).Select( x->x.Divizors ) . Where ( x-> x. Count = 4 ). PrintLines ; отобрать те элементы списка, где количество делителей равно 4 [1,2,5,10] [1,2,7,14] [1,3,5,15] 10 14 15
33 ( 10..20 ).Select( x->x.Divizors ) .Where( x-> x.Count = 4) . Select ( x-> (x[ 1 ],x[ 2 ] ) ). PrintLines ; заменить каждый элемент списка на пару ( кортеж ), состоящую из двух нетривиальных делителей (2,5) (2,7) (3,5) 10 14 15
34 ( Б.С. Михлин ) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [194441; 196500] простые числа, оканчивающиеся на 93.
35 ## uses school; ( 194441.. 196500 ) . Where ( x-> (x mod 100 = 93 ) and x. IsPrime ) . Println ; x. IsPrime ## uses school; ( 194493.. 196500 ). Step ( 100 ) . Where ( x-> x. IsPrime ) . Println ; . Step ( 100 ) 194493
36 Назовём натуральное число подходящим, если ровно два из его делителей входят в список (7, 11, 13, 19). Найдите все подходящие числа, принадлежащих отрезку [20 000; 30 000] В ответе запишите два целых числа: сначала количество, затем среднее арифметическое всех найденных чисел (только целую часть).
37 ## uses school; var selected := ( 20000.. 30000 ) . Select ( x-> x. Divizors ) . Select ( x->( x. Last, integer ( 7 in x)+ integer ( 11 in x)+ integer ( 13 in x)+ integer ( 19 in x)) ) . Where ( x-> x[ 1 ] = 2 ) . Select ( x->x[ 0 ] ); Println ( selected. Count, trunc ( selected. Average ) ); ord (... )
38 (7 0..91 ). Select ( x->x. Divizors ). PrintLines ; заменить каждый элемент последовательности на список его делителей [1,2,5,7,10,14,35,70] [1,71] [1,2,3,4,6,8,9,12,18,24,36,72] [1,73] [1,2,37,74] [1,3,5,15,25,75] [1,2,4,19,38,76] .. все делители 70
39 (7 0..91 ).Select( x->x.Divizors ) . Select ( x->( x. Last, integer ( 7 in x)+ integer ( 11 in x)+ integer ( 13 in x)+ integer ( 19 in x) ) ) . Println ; построить кортежи: ( число, количество делителей из [7,11,13,19] ) (70,1) (71,0) (72,0) (73,0) (74,0) (75,0) (76,1) (77,2) ..
40 (7 0..91 ).Select( x->x.Divizors ) .Select( x->( x.Last,...) ) . Where ( x-> x[ 1 ] = 2 ) . Println ; отобрать те, где количество делителей из списка ( x[1] ) равно 2: (77,2) (91,2)
41 (7 0..91 ).Select( x->x.Divizors ) .Select( x->( x.Last,...) ) .Where( x-> x[1] = 2 ) . Select ( x->x[ 0 ] ) . Println ; оставить только сами числа ( x[ 0 ] ) 77 9 1 вывести количество и среднее: Println ( selected. Count, selected. Average ); 2 84
42 ## var z:= ( 20000.. 30000 ) . Select ( x->(x, | 7, 11, 13, 19 |. Count (d-> x. Divs (d)) ) . Where ( x-> x[ 1 ] = 2 ) . Select ( x->x[ 0 ] ); Println ( z. Count, z. Average ); ## var z:= ( 20000.. 30000 ) . Where ( x->| 7, 11, 13, 19 | . Count (d-> x. Divs (d)) = 2 ); Println ( z. Count, z. Average ); два прохода по последовательности пары ( число, кол-во делителей )
43 (Статград) Найдите все натуральные числа, принадлежащие отрезку [289123456; 389123456] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель.
44 ## uses school; ( trunc ( sqrt ( sqrt ( 289123456 ))).. ceil ( sqrt ( sqrt ( 389123456 )))) . Where ( x-> x. IsPrime ) . Select ( x->x*x*x*x ) . Println ;
45 ( Демо-2021 ) Раз в неделю создаёт архив файлов. Объём диска, может быть меньше, чем суммарный объём файлов. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
46 https://kpolyakov.spb.ru/download/ege26.doc А. Сидоров: www.youtube.com/watch?v=LwTZAHsno0k
47 ## A ssign ( input, '26.txt' ); var (V, n) := ReadInteger2 ; var a := ReadArrInteger (n); a.Sort; var i := 0 ; while ( i <= a. High ) and (V >= a[ i ]) do begin V -= a[ i ]; i += 1 ; end ; i. Println ; V += a[i- 1 ]; while ( i <= a. High ) and (V >= a[ i ]) do i += 1 ; a[i- 1 ]. Print ; a. Sort ;
48 ## var A := | 27, 19, 21, 33 |; A. Sort ; A. Println ; 19 21 27 33 A. Sort ( (x,y)-> x mod 10-y mod 10 ); A. Println ; 21 33 27 19 A. Sort ( (x,y)-> y mod 10-x mod 10 ); A. Println ; 19 27 33 21 x mod 10-y mod 10 < 0 x < y = 0 x = y > 0 x > y . Sort переставляет элементы ! !
49 21 41 33 19 19 33 41 21 ## uses school; var A := | 41, 19, 21, 33 |; A. Sort ( (x,y)-> x.Digits.Sum-y.Digits.Sum ); A. Println ; A. Sort ( (x,y)-> y. Digits. Sum -x. Digits. Sum ); A. Println ; x. Digits. Sum -y. Digits. Sum по сумме цифр
50 ## var A := | 27, 19, 25, 33 |; A. Order. Println ; 19 25 27 33 A. OrderDescending. Println ; 33 27 25 19 . Order НЕ переставляет элементы и строит последовательность ! ! A. Sort ; A := A. Order. ToArray ;
51 ## var A := | 27, 19, 25, 33 |; A. OrderBy ( x->x mod 10 ). Println ; 33 25 27 19 A. OrderBy Descending ( x->x mod 10 ). Println ; 19 27 25 33 по последней цифре x->x mod 10
52 21 41 33 19 19 33 41 21 по сумме цифр ## uses school; var A := | 41, 19, 21, 33 |; A. OrderBy ( x->x.Digits.Sum ). Println ; A. OrderByDescending ( x->x. Digits. Sum ). Println ; x->x.Digits.Sum по сумме цифр
53 ( Е. Джобс ) В магазине проводят акция – каждый второй товар со скидкой 50%. При этом в акции участвуют только те товары, цены которых попадают в одну ценовую категорию. Каждая ценовая категория включает 500 целых значений: 1-500, 501-1000, 1001-1501 и т.д. Например, при наличии в чеке только позиций с ценами 300 и 1000 предложение акции не работает. Необходимо распределить товары в чеке таким образом, чтобы итоговая цена всех товаров была максимально выгодной для магазина. В качестве ответа вывести полученную сумму скидки для всего чека и конечную стоимость самого дорогого проданного по акции товара. В случае получения нецелых значений привести только целые части найденных чисел.
54 with open ( "26-44.txt" ) as F: N = int (F. readline ()) data = [] for i in range (N): data. append ( int (F. readline ()) ) data. sort () #... продолжение следует 1 1 0 1 2 … 500 505 510 … 998 1004 … chunk chunk chunk 1 1 0 1 2 … 320 330 … 450 500 chunk скидки
55 #... продолжение last = 500 discount, costMax = 0, 0 while data: chunk = [x for x in data if x <= last] if chunk: mid = len (chunk)// 2 if mid > 0 : discount += 0.5 * sum (chunk[:mid]) costMax = 0.5 *chunk[mid- 1 ] data = data[ len (chunk):] last+= 500 print ( int (discount), int (costMax) )
56 ## Assign (input, '26-44.txt' ); var N := ReadInteger ; var data := ReadArrInteger (N); data. Sort ; //... продолжение следует
57 #... продолжение var (last, discount, costMax ):= ( 500, 0.0, 0.0 ); while data. Count > 0 do begin var chunk := data. Where (x->x<=last). ToArray ; if chunk. Count > 0 then begin var mid := chunk. Count div 2 ; if mid > 0 then begin discount += 0.5 *chunk[:mid]. Sum ; costMax := 0.5 *chunk[mid- 1 ]; end ; data := data. Where (x->x>last). ToArray ; end ; last += 500 ; end ; Println ( trunc (discount), trunc (costMax) );
58 ( А. Кабанов ) На складе лежат пакеты с углём различного веса и стоимости. Вес и стоимость записаны на каждом пакете как натуральные числа. Для транспортировки отбираются K пакетов с самой низкой ценой угля за единицу веса; при равной стоимости за единицу веса выбираются пакеты с большим весом. По заданной информации о пакетах с углём и количестве транспортируемых пакетов определите суммарный вес угля в отправленных пакетах и стоимость самого тяжёлого отправленного пакета.
59 with open ( "26-k6.txt" ) as F: data = F. readlines () N, K = map ( int, data[ 0 ]. split ()) del data[ 0 ] data = data[:N] pairs = [] for i in range (N): p = tuple ( map( int, data[ i ].split()) ) pairs. append ( p ) #... продолжение следует строим массив пар ( вес, стоимость ) p = tuple ( map ( int, data[i]. split ()) )
60 #... продолжение pairs. sort ( key = lambda x: (x[ 1 ]/x[ 0 ], -x[ 0 ]) ) selected = pairs[:K] print( sum ( x[ 0 ] for x in selected ) ) weight = [x[ 0 ] for x in selected] ind = weight. index ( max (weight) ) print ( selected[ ind ][ 1 ] ) цена за единицу веса по убыванию веса суммарный вес стоимость пакета с наибольшим весом
61 ## Assign (input, '26-k6.txt' ); var (N, K):= ReadInteger2 ; var pairs := ( 1..N) . Select ( i -> ReadString. ToIntegers ) . Skip ( 1 ). ToArray ; pairs. Sort ( (x,y)-> x[ 1 ]/x[ 0 ]-y[1]/y[ 0 ] <> 0 ? sign (x[ 1 ]/x[ 0 ]-y[ 1 ]/y[ 0 ]) : y[ 0 ]-x[ 0 ] ); //... продолжение следует цена за единицу веса условие если верно по убыванию веса если неверно
62 #... продолжение var selected := pairs[:K]; var weight := selected. Select ( x->x[ 0 ] ). ToArray ; weight. Sum. Println ; var ind := weight. IndexOf ( weight. Max ); selected[ ind ][ 1 ]. Println ; суммарный вес стоимость пакета с наибольшим весом
63 В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар нечётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.
64 with open ( "26.txt" ) as F: N = int ( F. readline ()) data = [ int (s) for s in F] data. sort () averages = [] for i in range (N- 1 ): for j in range (i+ 1,N): if data[ i ] % 2 == 1 and data[j] % 2 == 1 : s = data[ i ] + data[j] averages. append ( s// 2 ) averages. sort () #... продолжение следует находим все подходящие средние
65 #... продолжение count = 0 ma = 0 for av in averages: if av in data: count += 1 ma = max ( ma, av ) print (count, ma) for av in averages: if av in data: сложность O ( N 2 )
66 9, 10, 14, 13, 8, 11 Все пары нечётных чисел: (9, 13) (9, 11 ) ( 13, 11 ) 11 1 0 12 Отсортируем ! ! 8, 9, 10, 1 1, 13, 1 4 1 0 1 1 12 Большее значение находится ближе к концу массива ! !
67 #... продолжение selected = [] i = 0 for av in averages: while i < N and data[i] < av: i += 1 if i < N and data[i] == av: selected. append (av) print ( len (selected), selected[ -1 ] )
68 ## Assign ( input, '26.txt' ); var N:= ReadInteger ; var data:= ReadArrInteger (N); data. Sort ; var averages := new List< integer >; for var i:= 0 to data. High - 1 do for var j:=i+ 1 to data. High do if data[i]. IsOdd and data[j]. IsOdd then averages. Add ((data[i]+data[j]) div 2 ); averages. Sort ; //... продолжение следует
69 ## Assign ( input, '26.txt' ); var N:= ReadInteger ; var data:= ReadArrInteger (N); data. Sort ; var averages := new List< integer >; foreach var ( x,y ) in data. Combinations ( 2 ) do if x. IsOdd and y. IsOdd then averages. Add ( ( x+y ) div 2 ); averages. Sort ; //... продолжение следует foreach var (x,y) in data. Combinations ( 2 ) do if x. IsOdd and y. IsOdd then averages. Add ( (x+y) div 2 ); или так:
70 #... продолжение var selected := new List< integer >; var i := 0 ; foreach var av in averages do begin while ( i < N) and (data[ i ] < av ) do i += 1 ; if ( i < N) and (data[ i ] = av ) then selected. Add ( av ); end ; Print ( selected. Count, selected. Last )
71 Благодарности Автор благодарит Алексея Богданова ( Alex Danov ) https://www.youtube.com/c/AlexDanov Станислава Михалковича https://pascalabc.net за полезные замечания и предложения.
72 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru
