Сообщение от genroelgvozo
Тогда свою задачу предложу тут
Она по типу задачи про фишку только чуть сложнее
Есть n автобусных остановок и m автобусных маршрутов каждый из которых задается начальной остановкой Si и конечно Ti
Это все вводится в программу в таком порядке
n m
S1 T1
S2 T2
------
Sm Tm
Вася приходит на остановку №1
он может сесть в i-ый автобус на любой его остановке о от Si до Ti-1 , но выйти только на конечной. Надо вывести количество способов добраться до n-ой остановки.
|
Задача как на меня - сложная. Если я не ошибаюсь в ней нужно знать хорошо комбинаторику и всякие формулы для комбинаций. Но я на этих уроках не был внимательным, поэтому сделал все через заднее место. (при помощи рекурсивной функции) Которая очень даже может быть неправильной. Я просто не знаю даже как проверить результат... Короче вот код:
Graphics 800,600,32,2
SetBuffer BackBuffer()
Global Time=MilliSecs()
Global Ansver=Funk(5,2)
Time=(MilliSecs()-time)*.001
Dim S(1)
Dim T(1)
Repeat
Cls
Text 10,10,"Operation time: "+Time
Text 10,20,Ansver
Flip
If KeyHit(1) End
Forever
Function Funk(N,M)
Local Ansver=0
Dim S(M)
Dim T(M)
For I=1 To M
S(I)=Rand(1,N-2)
T(I)=Rand(S(I)+1,N)
Next
For J=1 To m
If S(J)=1 Ansver=Ansver+Check(1,J,M,N)
Next
Return Ansver
End Function
Function Check(N,I,M_Max,N_Last)
Local Ansver
For X=N To T(I)
If N=N_Last Return 1
For Y=1 To M_Max
If X>=S(Y) And X<T(Y) Ansver=Ansver+Check(X+1,Y,M_Max,N_Last)
Next
Next
Return Ansver
End Function
Я проверял на варианте:
N=5
M=2
S1=2 T1=5
S2=1 T2=3
Ответ програмы - 8
Посчитал вручную - 8
Но все равно не уверен что правильно.
Кстати запустил вариант
N=10
M=15
Программа думала 104 секунды и выдала результат в 29 тысяч с копейками...
|
Ох, видели б вы киевскую районную
|
Первые три - ржач, вполне бы осилил.
Но в последней я даже смысл не понял
