Чт, 27.06.2019, 12:51
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

 
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Модератор форуму: Bandalak, Ktara, НІКОЛЯ, volevikt  
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Задачі шкільного рівня. (Методично правильні розв’язки цікавих задач шкільної прогр.)
Задачі шкільного рівня.
Ковальчук_Олександр Дата: Вт, 11.03.2008, 02:09 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3705
Нагороди: 18
Рейтинг: 209
У гостьовій книзі користувач роман попросив розв’язати кілька простих задач для свого сина.
Я вирішив допомогти йому і заодно створити тему, де хтось буде писати умову цікавої задачі шкільного рівня, а інші будуть пропонувати розв’язки цієї задачі. І ми разом серед кількох варіантів розв’язку вибиратимемо найоптимальніший, методично правильний. Тема досить актуальна і цікава. Сподіваюсь, допоможе вчителям, які з різних причин погано знаються на задачах з програмування навіть шкільного рівня (наприклад вчитель, який інформатику читає не за спеціальністю).

Отож, задачі з гостьової книги:
Задача 1. Дано натуральне число N (1000 < =N<=9999). Визначити, чи є числo поліндромом, тобто таким числом, яке зліва направо і справа наліво читається однаково (всі чотири цифри враховуються; наприклад, 0110).
Задача 2. Василина Премудра грала в шашки зі змієм Гориничем на дуже великій дошці. Спочатку Василина з’їла у Горинича 3 шашки, а Горинич у Василини – 5 шашок, потім Василина у Горинича з’їла 9 шашок, а Горинич у Василини – 10 шашок, на третьому ході Василина проковтнула 15 шашок, а Горинич- 20. Ця серйозна гра тривала ще довго, аж поки Горинич не втомився і після N-го ходу не з’їв саму Василину. Скільки всього шашок проковтнув Змій Горинич? Кількість шашок завжди достатня.
Задача 3 . Знайти всі дільники натурального числа N.

Розв’язки:
Задача 1.
var n,n1,n2,n3,n4,r:integer;
begin
write('Введіть будь-яке чотирьохзначне число: ');
readln(n);
n1:=n div 1000;
n2:=(n div 100) mod 10;
n3:=(n div 10) mod 10;
n4:= n mod 10;
r:=n4*1000+n3*100+n2*10+n1;
if r=n then writeln ('Введене число ',n,' являється поліндромом.')
else writeln ('Введене число ',n,' не є поліндромом.')
end.
Задача 3.
var i,n:integer;
begin
writeln('Введіть натуральне число');
readln(n);
writeln('Дільники числа ',n,': ');
for i:=1 to n do
if n mod i = 0 then
write(i,' ');
end.

Розв’язок задачі 2 напишу незабаром.
А зараз хотілося б почути ваші думки з приводу того, чи оптимально розв’язані задачі 1 та задачі 3.
Звичайно, задача 1 не враховує захист від введення не чотиризначного числа, та це легко можна виправити розгалуженням.


Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!!

filnick Дата: Чт, 06.11.2008, 22:16 | Повідомлення № 91
Мудрий вчитель
Повідомлень: 2238
Нагороди: 7
Рейтинг: 124
Quote (vitert)
що 0^y, якщо у>0 також невизначеність, що більш очевидно

Ви мали на увазі у<0.
Quote (vitert)
У визначенні степеневої функції я нічого про це не найшов

Підручник "Алгебра та початки аналізу 10 клас". Автори Шкіль М.І., Слєпкань З.І., Дубинчук О.С. Київ: Зодіак-ЕКО, 2002р. стор. 174 п.18 тема "Узагальнення поняття степеня. Степенева функція".
Quote (KulAlex)
у розділі показникова функція дійсно написано

З показниковою функцією все досить елементарно і ясно: у=а^x , при a<0 і a=1 це вже не функція. А мова йде саме про степеневу, тобто у=x^p, де залежно від основи х та показника р можливі варіанти:
1) р - натуральне число. (три випадки: р=1, р - непарне і р - парне число);
2) р - ціле від'ємне число (два випадки: р - непарне і р - парне число);
3) р - дробове число виду 1/k (де k = 2; 3; 4 ...)
і т.д.
vitert Дата: Пт, 07.11.2008, 01:40 | Повідомлення № 92
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (filnick)
Ви мали на увазі у<0.

Ви праві, звичайно я говорив про це.
Quote (filnick)

З показниковою функцією все досить елементарно і ясно: у=а^x , при a<0 і a=1 це вже не функція.

При а=1 це також функція, щоправда не показникова (чи може функціонал не пам'я таю зараз не в цьому суть)

Quote (filnick)
А мова йде саме про степеневу, тобто у=x^p, де залежно від основи х та показника р можливі варіанти: 1) р - натуральне число. (три випадки: р=1, р - непарне і р - парне число); 2) р - ціле від'ємне число (два випадки: р - непарне і р - парне число); 3) р - дробове число виду 1/k (де k = 2; 3; 4 ...) і т.д.

Ви намагаєтесь все строго підлаштувати під математичні правила, точніше визначення, як на мене цього не потрібно робити. В нас є задача написати програму, яка знаходить х^y, де xЄR, yЄQ, я все ж таки пропоную поки, що зупинтися на раціональному показнику перш ніж переходити до дійсного, поки не буде написана прога яка це робить (хоча з ірраціональним показником може і не бути проблем, sqrt(2) можна вводити як рядкову величниу "к2" і якщо я не помиляюсь степінь з відємною основою з іраціональним показником завжди існує і завжди відємний, тому тому тут для відємної основи таких складнощів не буде, але ще не впевнений).
Для даної програми є лише дві умови:
1) вона працює правильно для будь-якого випадку
2) вона є оптимальною із усіх можливих
Тому я пропоную показниковою (можна уявно-показниковою якщо бажаєте) називати функцію для якої основа фіксована, а показник проходить всю множину чисел. Степенева це функція де показник фіксований, а снова проходить всю множину. Тобто якщо ми розбиваємо проміжки по показнику, як ви пропонуєте, то функція степенева, якщо по основі то показникова.
Яка різниця, що в математиці функція y=a^x при х=1 не називається показниковою, якщо 1 підноситься до будь-якого степеня так само як будь-яке додатнє число і при умові x>0 буде так само буде обчислюватись за формулою exp(y*ln(x)).
Тому я пропоную слідуючі варіанти:
I. (x=0)or(y=0) 1) (x=0)and(y<=0)
........................2) (x=0)and(y>0)
........................3) (x<>0)and(y=0)

II. x>0 1 випадок

III. x<0 1) у=m/n; (НСД(m,n)=1); n mod 2=0 функція не визначена
.............2) у=m/n; (НСД(m,n)=1); (n mod 2<>0)and (m mod 2=0); x^y=exp(y*ln(abs(x)))
.............3) у=m/n; (НСД(m,n)=1); (n mod 2<>0)and (m mod 2<>0); x^y=-exp(y*ln(abs(x)))

Всього сім випадків. І оскільки я розглядаю поділ по основі, дана дана функціє є показниковою, крім першого випадку, який можна назвати вийнятком.
Напишіть усі випадки якщо розглядати дану функцію як степеневу, як на мене їх більше, а значить мій варіант оптимальніший. Але це поки, що тільки теорія, коли прога буде працювати, і працювати правильно тоді і можна буде робити якісь висновки, можливо в 3 випадку в мене помилки, я ще не перевірив.

Відредаговано: vitert - Пт, 07.11.2008, 01:48
filnick Дата: Пт, 07.11.2008, 19:35 | Повідомлення № 93
Мудрий вчитель
Повідомлень: 2238
Нагороди: 7
Рейтинг: 124
Цікаво дізнатися, як побудований алгоритм обчислення в Excel (там рахує вірно з від'ємними, додатніми і нульовими значеннями основи та показника)
vitert Дата: Сб, 08.11.2008, 03:17 | Повідомлення № 94
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (filnick)
Цікаво дізнатися, як побудований алгоритм обчислення в Excel (там рахує вірно з від'ємними, додатніми і нульовими значеннями основи та показника)

спробуйте написати (-128)^(-5/7) або (-128)^(5/7)?
Там мабуть написали окремі випадки для найбільш поширених показників 1/2, 1/3, 1/4 і.т.д. 1/5 працює а уже 3/5 ні.

Додано (08.11.2008, 03:17)
---------------------------------------------
Написав код для обчислення степеня з раціональним показником, прада ще потрібно трохи оптимізувати. Подивіться і висловіть зауваження. Пізніше добавлю для дійсного показника. Як недолік відсутність перевірки введення показника.

program dil;
uses crt;
var x,y:real;
s:string;
ch,zn:integer;

procedure nsd(m,n:integer; var d:integer);
var max,min:integer;
begin
if m>n then begin max:=m; min:=n end else begin max:=n; min:=m end;
while max mod min<>0 do begin
max:=max-min;
if min>max then begin max:=min+max;min:=max-min;max:=max-min end;
end;
d:=min;
end;

procedure peret(s:string; var y:real;var ch,zn:integer);
var pm,pk,ps,pd,l,code,zil,nd:integer;
chl:string;
begin
pm:=pos('-',s);
if pm=1 then s:=copy(s,2,length(s));
l:=length(s);
pk:=pos('.',s);
ps:=pos(' ',s);
pd:=pos('/',s);
if (pk=0)and(ps=0)and(pd=0) then val(s,y,code);
if (pk<>0)and(ps=0)and(pd=0)then begin
val(copy(s,1,pk-1),zil,code);
chl:=copy(s,pk+1,l);
val(chl,ch,code);
zn:=trunc(exp(length(chl)*ln(10)));
end;
if (pk=0)and(ps=0)and(pd<>0) then begin
val(copy(s,1,pd-1),ch,code);
val(copy(s,pd+1,l),zn,code);
end;
if (pk=0)and(ps<>0)and(pd<>0) then begin
val(copy(s,1,ps-1),zil,code);
val(copy(s,ps+1,pd-1),ch,code);
val(copy(s,pd+1,l),zn,code);
end;
if ch<>0 then begin
nsd(ch,zn,nd);
ch:=trunc(ch/nd);zn:=trunc(zn/nd);
y:=(zil*zn+ch)/zn;
end;
if pm=1 then y:=-y;
end;

function pow(x:real;s:string):real;
begin
peret(s,y,ch,zn);
if (x=0)or(y=0) then begin
if (x=0)and(y<=0) then halt(1)
else if(x=0)and(y>0) then pow:=0 else pow:=1
end
else begin
if x>=0 then pow:=exp(y*ln(x))
else if zn mod 2=0 then halt(1)
else begin if ch mod 2=0 then pow:=exp(y*ln(abs(x)))
else pow:=-exp(y*ln(abs(x)))
end
end
end;

begin
clrscr;
Write('Введіть основу степеня x=');readln(x);
writeln('Введіть показник степеня, якщо звичайний дріб то в форматі m/n чи z m/n');
writeln('(Де z-ціла частина, m-чисельник n-знаменник)');
write('y=');readln(s);
writeln(pow(x,s));
end.

Відредаговано: vitert - Сб, 08.11.2008, 03:18
filnick Дата: Сб, 08.11.2008, 13:15 | Повідомлення № 95
Мудрий вчитель
Повідомлень: 2238
Нагороди: 7
Рейтинг: 124
Quote (vitert)
Там мабуть написали окремі випадки для найбільш поширених показників 1/2, 1/3, 1/4 і.т.д. 1/5 працює а уже 3/5 ні.

А це якраз і є третій випадок, згаданий у моєму пості № 93 на цій гілці. Видно-таки в Екселі все строго підлаштовано під математичні визначення.
vitert Дата: Сб, 08.11.2008, 17:58 | Повідомлення № 96
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (filnick)
А це якраз і є третій випадок, згаданий у моєму пості № 93 на цій гілці.

Так, але чому потрібно окремий випадок для показника 1/n, чому не брати m/n адже там всього на одну умову більше???

А що таке степінь з ірраціональним показником? З натуральним, цілим, раціональним зрозуміло, а як дається визначення ірраціонального показника, як піднести 2 до степеня sqrt(2), результат буде ірраціональний, тому можна обчислювати лише наближено. І чи правильно те твердження, яке я писав вище, що степінь з від'ємною основою і іраціональним показником завжди існує і завжди від'ємний.

filnick Дата: Сб, 08.11.2008, 20:05 | Повідомлення № 97
Мудрий вчитель
Повідомлень: 2238
Нагороди: 7
Рейтинг: 124
Quote (vitert)
чому потрібно окремий випадок для показника 1/n, чому не брати m/n адже там всього на одну умову більше???

Можливо тому, що m/n=(1/n)*m і тоді степінь з раціональним показником зводиться до кореня n-го степеня з а, піднесеного до степеня m.
Quote (vitert)
А що таке степінь з ірраціональним показником?

Степінь з ірраціональним показником а^x розглядається тільки для а>0. Для від'ємних а степеня з ірраціональним показника не існує.
vitert Дата: Пн, 10.11.2008, 00:53 | Повідомлення № 98
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (filnick)
Можливо тому, що m/n=(1/n)*m і тоді степінь з раціональним показником зводиться до кореня n-го степеня з а, піднесеного до степеня m.

Так ви, мабуть праві, замість -128^(5/7) потрібно написати (-128^1/7)^5 і так буде працювати, тому в екселі задача піднесення до буд-якого степеня будь якого числа розв'язана. Тому можна ще споробувати написати прогу розглядаючи х^y як степеневу функцію, вона буде не набагато неоптимальніша за ту яку я написав, зате більш теоритично обгрунтована. Окільки зауважень до моєї проги не було, не знаю чи її хтось дивився, думаю ми це питання вичерпали, для іраціонального показника немає сенсу писати, оскільки при від'ємній основі степінь не існує, хоча уточніть не існує для дійсних чисел чи для будь-яких. Я правда ще для себе спробую написати кілька варіацій даної проги, оптимізую.

Одна із задач, з тих що регулярно приносять для студенти іт факультетів:
Тема - анімація в паскалі. Коротка умова, що потрібно зробити: йде слон і махає вухами.

Я думаю непогано було б створити базу задач, цікавих, різнорівневих, з різних тем шкільного курсу, які тут обговорити знайти оптимальні правильні роз'язки, написати коментарі. Причому розв'язати на різних мовах, наприклад: Pascal (мова №1 шкільного курсу, щоправда немає практичного застосування, одне слово навчальна), C++(класика жанру), VB(візуальне програмування - адаптоване для windows), PHP (програмування для веб-інтерфейсу - перспективно, наглядне застосування прогамування) можана ще й excel добавити, там де це можливо.
Для того, щоб зацікавити учнів програмуванням, та і не тіки зацікавити а показати що вміння програмувати є корисним у багатьох випадках, і не сильно відрізняється у різних середовищах, є універсальним інструментом для розв'язування багатьох задач, я думаю варто використовувати не лише одну мову, повинна бути базова мова і кілька мов домоміжних, які допоможуть реалізувати написане вище. Напиклад розглядаючи розгалудження можна на уроці розв'язати 2, 3, 4, чи 5 задач (хоча іноді і однієї вистачає, точніше рівня учнів вистачає на одну задачу) а можна розв'язати її повністю на базовій мові, а потім розглянути її в інших середовищах маючи готові заготовки і вписавши наприклад лише умову так як вона пишеться в кожній мові, звичайно не на кожному уроці, а коли бачиш у цьому необхідність. Звичайно вчителеві для цього самому потрібно знати кілька мов, тому я і думаю що ця пропозиція буде корисна, адже маючи маючи задачу розв'язану і пояснену на різних мовах ти без проблем можеш розібратися, освоїти кілька мов, адже тут є люди які це знають і вміють.
Я наприклад, намагаюся використовувати крім паскаля, С++, PHP, Excel (лінійні і розгалуджені програми), на VB тільки цим літом почав писати - ще в процесі. Минулий рік навіть подумував взяти PHP як базову мову, оскільки в учнів був гурток веб-дизайну то трішки мали уявлення про роботу з формами, HTML, але я ще сам не достатньо вивчив PHP тому поки, що це лише додаткова мова, іноді.

Щодо задач то серед тих які тут розглядалися можна взяти задачу з повідомлення №1 про знаходження всіх дільників числа n - тема цикли. На прикладі неї можна показати поняття оптимізації - 1 варіант цикл до n, 2 - до n/2, 3- до sqrt(n). На паскалі написано пропоную написати на C++, VB, PHP, або запропонуйте інші мови обгрунтувавши чому.

2 задача, також повідомлення №1 про шашки і Василину також тема цикли, є цікавий момент із шашками що з'їла Василина, перевірити як працює логіка в учнів.

3 задача про яку ми говорили останнм часом писали про піднесення до степеня будь-якого числа, щоправда краще зупинитись на десяткових дробах, чи цілих показниках, для школи достатньо. Тут же є ще задача про перетворення десяткових дробів у звичайні - рядкові величини.

Тільки сумніваюсь, що ідея буде реалізована, мало народу заходить на цю вітку, та і програмуванням мало цікавляться, і часу це багато займає.

dpi Дата: Пт, 21.11.2008, 21:18 | Повідомлення № 99
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Quote (vitert)
На прикладі неї можна показати поняття оптимізації - 1 варіант цикл до n, 2 - до n/2, 3- до sqrt(n).

Не увлекайтесь оптимизацией и оригинальностью кода. Нет реальной пользы, другим трудно читать ваш код, потеря времени. (Конечно, если не привышаете время выполнения программы.)

vitert Дата: Пт, 21.11.2008, 21:33 | Повідомлення № 100
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (dpi)
Не увлекайтесь оптимизацией и оригинальностью кода. Нет реальной пользы, другим трудно читать ваш код, потеря времени.

Це случайно не слоган Microsoft?
dpi Дата: Пт, 21.11.2008, 23:29 | Повідомлення № 101
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Это большая часть из книги Голуба А.И. "Правила программирования на С и С++", а на счет времени из личного опыта.
zivert Дата: Пт, 28.11.2008, 09:16 | Повідомлення № 102
Тут живе...
Повідомлень: 178
Нагороди: 2
Рейтинг: 48
Колеги, пропоную до розгляду цікаву задачу з програмування :
"Сашко, учень 11 класу, готував домашнє завдання з української літератури, твір-роздум на тему: "Ярослав Мудрий - художнє втілення ідеї незалежності народного духу, любові й відданості своєї Вітчизни". Оскільки він не був майстром пера, то взявся до розв'язання логічних завдань, які Сашко дуже полюбляв виконувати, коли йому було нудно. Сашкові стало цікаво, скільки різних комбінацій прямокутника можливо скласти з лінійок двох типів шириною 1 см та довжиною 2 і 3 см. Розміри прямокутника 8*5 см. Лінійки розкладати по периметру прямокутника, так, щоб ширина контуру була незмінною, тобто 1 см. Кількість лінійок не обмежена. Допоможіть Сашкові розв'язати цю складну задачу, інакше Галина Іванівна, вчителька української літератури, виставить в журнал двійку за невиконане домашнє завдання."
al-kov Дата: Пт, 28.11.2008, 11:19 | Повідомлення № 103
Часто заходить...
Повідомлень: 91
Нагороди: 1
Рейтинг: 18
Це задача на комбінаторику треба скористатися правилом
http://www.college.ru/mathema....ry.html
Див. Приклад 4
dpi Дата: Пт, 28.11.2008, 12:22 | Повідомлення № 104
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
zivert, спасибо за задачу.
Со всех разновидностей задач это у меня самое слабое место.
На первый взгляд комбинаторная задача. Начал подбирать (перебирать), появилась идея попробовать методом перебора. На листе вручную пришел к числу 68 (подскажите хоть правильно или нет).
Буду очень благодарен за подробное объяснения алгоритма решения.
Кроме этой, уже две подобные задачи на различных олимпиадах были пропущены (не решены кирпичи, плитки и т.п.), которые стояли первыми в списе, т.е. самыми легкими считались.

Додано (28.11.2008, 12:22)
---------------------------------------------

Quote (al-kov)
Це задача на комбінаторику треба скористатися правилом
http://www.college.ru/mathema....ry.html
Див. Приклад 4

Спасибо за ссылку.
filnick Дата: Пт, 28.11.2008, 18:38 | Повідомлення № 105
Мудрий вчитель
Повідомлень: 2238
Нагороди: 7
Рейтинг: 124
Quote (zivert)
скільки різних комбінацій прямокутника можливо скласти з лінійок двох типів шириною 1 см та довжиною 2 і 3 см. Розміри прямокутника 8*5 см. Лінійки розкладати по периметру прямокутника, так, щоб ширина контуру була незмінною, тобто 1 см. Кількість лінійок не обмежена.

Площа периметру лінійок дорівнює 22 кв.см.
Існує 9 варіантів співрозміщень прямокутних смужок на сторонах, щоб утворити прямокутник за даними розмірами:
1) 6 - 4 - 8 - 4
2) 6 - 4 - 7 - 5
3) 6 - 5 - 6 - 5
4) 6 - 5 - 7 - 4
5) 7 - 3 - 8 - 4
6) 7 - 3 - 7 - 5
7) 7 - 4 - 7 - 4
8) 8 - 3 - 7 - 4
9) 8 - 3 - 8 - 3
Тепер залишається визначити скількома способами можна представити кожну смужку
3 см - 1 (одна 3 сантиметрова лінійка)
4 см - 1 (дві 2 см лінійки)
5 см - 2 ( одна 3 см +одна 2 см)
6 см - 2 ( дві 3 см або 3 двохсантиметрових)
7 см - 3 (2 х 2 см + 1 х 3 см (3 перестановки) )
8 см - 11 (4 х 2 см (1), або 3 х 2 см + 1 х 3 см (4), або 1 х 2см + 2 х 3 см (6 перестановок)).
Таким чином, для першого варіанту можливо : 2*1*11*1=22 способи
для
2) 2*1*3*2 =12
3) =2*2*2*2=16
4) = 2*2*3*1=12
5) =3*1*11*1=33
6) =3*1*3*2=18
7) =3*1*3*1=9
8) =11*1*3*1=33
9) =11*11=121
Всього: 276 способів.

Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Задачі шкільного рівня. (Методично правильні розв’язки цікавих задач шкільної прогр.)
Пошук:


© Форум інформатиків України, 2007-2019.