А ш ы қ саба қ Пән: "Информатикадан олимпиадалық есептерді шешу әдістемесі"

Студенттердің есепті шығаруы және талқылаулары және бағдарлама нәтижелерін алу (35 мин)

жүктеу/скачать 32,36 Kb.

бет	4/4
Дата	24.11.2023
өлшемі	32,36 Kb.
	#125435
түрі	Сабақ

1 2 3 4

Студенттердің есепті шығаруы және талқылаулары және бағдарлама нәтижелерін алу (35 мин)
Келесі кезекте студенттер олимпиада тапсырмаларының шарттарын түсіндіреді. Конференция барысында баяндамашылар басқа студенттер жауап беруі керек сұрақтар қоя алады.

Acmp.ru сайтының “Динамикалық бағдарламалау” бөлімінің есептерін талдау.

Динамика - 1
Есеп 554. Пицца.
#include
using namespace std;
int main()
{ int n; cin >> n; cout << (n + 1) * n/2 + 1;
return 0;
}
Есеп 121. Шегелер
n = int(input()) lst = [int(i)
for i in input().split()]
lst.sort() d = [0] * n d[1] = lst[1] - lst[0]
if n > 2: d[2] = lst[2] - lst[0]
for i in range(3, n):
d[i] = min(d[i - 2], d[i - 1]) + lst[i] - lst[i - 1]
print(d[n - 1])

№114. Қатар тұрған екі нольсіз

№	INPUT.TXT	OUTPUT.TXT
1	2 10	90
2	4 2	5
3	6 3	328

#include
#include
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector c(n + 1);
c[1] = k - 1;
c[2] = k * (k - 1);
for (int z = 3; z <= n; z++)
c[z] = (k - 1) * (c[z - 1] + c[z - 2]);
cout << c[n];
return 0;}
Есеп 544. Баспалдақтағы доп.
n, t = int(input()), {-2: 0, -1: 0, 0: 1}
for i in range(1, n + 1):
t[i] = t[i - 1] + t[i - 2] + t[i - 3]
print(t[n])
№11. Қоян

№	INPUT.TXT	OUTPUT.TXT
1	1 3	1
2	2 7	21
3	3 10	274

k,n = map(int,input().split())
d = [1]+[1]+[0]*(n-1)
for i in range(2,len(d)):
if i-k<0:
for j in range(0,i):
d[i] += d[j]
else:
for j in range(i-k, i):
d[i] += d[j]
print(max(d))
Динамика - 2
№29. Компьютерлік ойын

№	INPUT.TXT	OUTPUT.TXT
1	3 1 5 10	9
2	3 1 5 2	3

n = int(input())
heights = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0

for i in range(1, n):

dp[i] = dp[i - 1] + abs(heights[i] - heights[i - 1])
if i >= 2:
dp[i] = min(dp[i], dp[i - 2] + 3 * abs(heights[i] - heights[i - 2]))
min_energy = dp[n - 1]
print(min_energy)

Динамика - 3
№525. Екінің дәрежелерінің қосындысы

№	INPUT.TXT	OUTPUT.TXT
1	4	4
2	7	6

#include
#include
using namespace std;
int main() {int n; scanf("%d", &n);
std::vector count(1+n);
count[0]=1; count[1]=1;
for (int i=2;i<=n;i++){ count[i]=count[i-2]+count[i/2];}
printf("%d",count.back()); return 0;}

Динамика - 5
№16. Баспалдақ

№	INPUT.TXT	OUTPUT.TXT
1	3	2
2	6	4

def kubik(n):
a = [1]+[0]*n
for i in range(1,n+1):
for j in range(n,i-1,-1):
a[j]+=a[j-i]
return a[n]
print(kubik(int(input())))

Сабақты бекіту (5 мин)
Студенттердің сабақта алған білімдері бойынша қорытынды жасау мақсатында оқытушы бекіту сұрақтарын қояды.

Динамикалық бағдарламалаудың мәні неде?
Динамикалық бағдарламалау әдісінің стратегиясы деген не?
Жоғарыдан төменге динамикалық бағдарламалау қалай жүзеге асады?
Төменнен жоғарыға динамикалық бағдарламалау дегенді қалай түсінесіз?

Рефлексия (3 мин)
Мысалы, келесідей сұрақтар болуы мүмкін:

Конференция ұнады ма?
Таңдалған тақырып қызықты болды ма?
Тақырып бойынша бұрын не білдіңіз?
Бұл тақырып бойынша қандай жаңа нәрсені білдіңіз?

Үйге тапсырма (1 мин) Acmp.ru сайтының “Динамикалық бағдарламалау” бөлімінің басқа да есептерін шығарып, талдау.
Қорытынды бөлімде (1 мин) бағалар қойылып, конференция-сабаққа белсене қатысқан студенттер аталады.
Әдебиеттер:

Мальцев, С. П. Олимпиадное программирование : учебно-методическое пособие / С. П. Мальцев. — БГУ, 2019. — 135 с. — ISBN 978-59793-1396-2. URL: https://e.lanbook.com/book/154258

Колдаев, В. Д. Сборник задач и упражнений по информатике : учебное пособие. — Москва : ФОРУМ : ИНФРА-М, 2022. — 255 с.
http://acmp.ru

жүктеу/скачать 32,36 Kb.

Достарыңызбен бөлісу:

1 2 3 4