Лекција од 5 одделение 39 - 26.05.2015 година - Алгопедија
Содржина
Discussе разговараме за некои класични проблеми, со или без вектори.
Моќност
Пресметајте што е можно поефикасно n (а и n природни броеви). Проблемот е познат и како логаритамски пораст. Идејата зад ова решение е ова:
- Ако n е парен, тогаш a n = a 2 * n/2 = (a 2) n/2
- Ако n е непарен, тогаш n-1 е парен и имаме an = a * a n-1 = a * a 2 * (n-1)/2 = a * (a 2) (n-1)/2 = a * (a 2) n/2
Во горенаведените формули сметавме дека/е интегрална поделба на јазикот C. Затоа, кога n е непарен (n-1)/2 е исто што и n/2. Забележано е дека без оглед на паритетот на n, на секој чекор од повторувањето можеме да претвориме a во a * a, а потоа n да го поделиме со 2. Само во случаи кога n е непарен, ќе ја акумулираме тековната вредност на a во пресметаниот производ. Еве го решението засновано на оваа идеја:
Монотона низа
Кажете дали низата броеви е монотона. Низата е монотона ако нејзините броеви се или во растечки или опаѓачки редослед. Низата има најмалку два броја. Не смеете да користите низи (вектори или матрици).
заграда
Со оглед на низа од 0 и 1, каде што 0 значи отворена заграда '(', а 1 значи затворена заграда ')', кажете дали низата е правилен израз на загради и ако е така пресметајте го максималниот број на загради едни во други. Пример: 0 1 0 0 1 0 1 1 е точен и има фактор на гнездење 2, додека низата 0 0 0 1 1 1 0 е неточна. Не смеете да користите низи (вектори или матрици).
Можеме да го решиме проблемот со почитување на следниве правила валидни за секој правилен израз:
- каде и да го „скршиме“ изразот, лево ќе имаме голем број отворени загради поголеми или еднакви на затворените
- на крајот бројот на затворени загради мора да биде еднаков на затворените
Ако се исполнети двата услови, изразот е точен. Првиот услов мора да биде исполнет за секоја позиција на кршење.
Тема за домашна работа: како генерализираме? Имаме кружни загради, квадрати и загради, истото барање.