TI/Programowanie dla Fizyków Medycznych:Ciekawe zadania

Ciekawe zadania

powrót: Programowanie dla fizyków medycznych

Zadanie 1

Masz dwa ciągi w formie list. Podciągiem nazwiemy dowolny podzbiór elementów wyjętych z ciągu, ułożonych w tej samej co wcześniej kolejności. Np.

• [1, 3, 5] jest podciągiem ciągu [0,1,2,3,4,5]
• [1, 2, 1] jest podciągiem ciągu [0,1,2,3,2,1,0].

Zadnie polega na znalezieniu najdłuższego wspólnego podciągu danych ciągów.

Powinna zostać zdefiniowana funkcja, która na wejściu dostaje po przecinkach jako parametry podane ciągi, a zwraca wartość int, odpowiadającą długości najdłuższego podciągu.

Zastanów się: Jaka jest złożoność zastosowanego przez Ciebie algorytmu? Jak można zadanie uprościć? Czy mogłyby się do czegoś przydać te ciągi posortowane?

Zadanie 2A

Masz współrzędne trzech punktów A, B, C wyznaczających wierzchołki trójkąta oraz współrzędne punktu P. Zadanie polega na sprawdzeniu, czy punkt P znajduje się wewnątrz trójkąta (lub na jego krawędzi).

Powinna zostać zdefiniowana funkcja, która na wejściu dostaje cztery krotki (xA, yA), (xB, yB), (xC, yC), (xP, yP) i zwraca True, jeśli punkt P spełnia powyższy warunek.

Aby sprawdzić, czy zadanie dobrze zostało rozwiązane, zwizualizujmy je z pomocą biblioteki matplotlib.pyplot:

import matplotlib.pyplot as plt

Wierzcholki=[(1,2),(2,3),(4,2)] #lista wierzchołków trójkąta
P=(7,8) #współrzędne punktu do sprawdzenia

#rysowanie wierzchołków
#lista krotek zostaje zamieniona na dwie listy współrzędnych x i y: [1,2,4] i [2,3,2]
plt.plot([I[0] for I in Wierzcholki], [I[1] for I in Wierzcholki], "*k")

#rysowanie krawędzi
#do list współrzędnych dodano pierwszy punkt, żeby trójkąt się zamknął
plt.plot([I[0] for I in Wierzcholki]+[Wierzcholki[0][0]], [I[1] for I in Wierzcholki]+[Wierzcholki[0][1]], "-k")
plt.plot(P[0], P[1], "*r")

#ustawianie granic widocznej części obrazu
plt.xlim(0,10)
plt.ylim(0,10)

Podpowiedź: Jeśli punkt P znajduje się wewnątrz trójkąta ABC, wówczas jeśli spróbujemy wyrazić wektor PC przez kombinację wektorów PA i PB: [math]\overrightarrow {PC}=a \overrightarrow {PA}+b \overrightarrow {PB}[/math], oba współczynniki a i b będą miały wartości ujemne.

Zadanie 2B

Masz zbiór punktów, z których część wyznacza krawędzie wypukłego wielokąta, a pozostałe znajdują się wewnątrz wielokąta. Sprawdź które to punkty.

Powinna zostać zdefiniowana funkcja, która na wejściu otrzyma listę krotek wyznaczających punkty [(xA, yA), ...], a na wyjściu zwraca listę krotek wyznaczających tylko punkty wyznaczające krawędzie zewnętrznego wypukłego wielokąta.

Działanie programu powinno zostać zwizualizowane - najpierw stan wejściowy, potem stan wyjściowy.

Zadanie 2C

Zbiór punktów stanowiących wierzchołki wielokąta otrzymany w zadaniu 2B przerobić na zbiór trójkątów w taki sposób, by ich krawędzie się nie przecinały.

Powinna zostać zdefiniowana funkcja, która na wejściu ma listę współrzędnych wierzchołków [(xA, yA), ...], a na wyjściu listę trójek współrzędnych [((xA, yA), (xB, yB), (xC, yC)), ...]

Podpowiedź: Wielokąt wypukły może być zbudowany z wielu trójkątów mających jeden wierzchołek wspólny.

Zadanie 3

Masz układ n równań liniowych. Rozwiąż go, eliminując kolejne zmienne przez mnożenie stronami i odejmowanie stronami równań.

[math] \\ ax+by=c \ |\cdot d \\ dx+ey=f \ |\cdot a \\ \\ adx+bdy=cd \\ adx+eay=fa \\ - \\ (bd-ea)y=cd-fa \\ y=\frac {cd-fa}{bd-ea} [/math]

Na wejściu funkcji rozwiązującej układ równań powinna znaleźć się lista list reprezentujących współczynniki w kolejnych równaniach, np. [[1,2,3],[2,3,4]].

Przydatna będzie druga funkcja, która będzie dostawała na wejściu współczynniki układu n równań, a na wyjściu będzie zwracała współczynniki układu n-1 równań, nie zawierające pierwszej zmiennej.

Zagadki

Jak tworzyć łatwo wieloelementowe listy? Na co uważać? Wyjaśnij działanie poniższego kodu:

l1=[0]*10
l1[3]+=1
print('l1:\n',l1)
l2=[[0]]*10
l2[3].append(1)
print('l2:\n',l2)
l3=[[0] for x in range(10)]
l3[3].append(1)
print('l3:\n',l3)
l4=[x for x in range(10)]
print('l4:\n',l4)

Jak posortować listę w taki sposób, by nie stracić informacji o pierwotnych indeksach?

l1=list('Ala ma kota')
print('l1:\n',l1)
l2=sorted(l1)
print('l2:\n',l2)
l3=list(enumerate(l1))
print('l3:\n',l3)
l4=sorted(l3, key=lambda x: x[1])
print('l4:\n',l4)

Jak wypisać wszystkie możliwe podciągi ciągu zapisanego w postaci listy?

l1=list(bin(5))[2:]
print('l1:\n',l1)
l2=['0']*3+l1
print('l2:\n',l2)
l3=list('{:0>6}'.format(bin(5)[2:]))
print('l3:\n',l3)

ciag=[5,10,15]
print('ciag:\n',ciag)
print('podciagi:')
for i in range(2**len(ciag)):
    b=list(bin(i)[2:])
    l4=['0']*(len(ciag)-len(b))+b
    podciag=[ciag[x] for x in range(len(ciag)) if l4[x]=='1']
    print (podciag)