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?

Programowanie dla fizyków medycznych

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.

Rozwiązanie:

# -*- coding: utf-8 -*-
"""
Created on Fri Dec 15 14:44:34 2017

@author: jginter
"""

def czywewnatrz(A,B,C,P):
    #zwraca 0 gdy P na zewnatrz trojkata,
    #1 - wierzcholek, 2 - na krawedzi, 3 - wewnatrz
    xA=A[0]-P[0]
    yA=A[1]-P[1]
    xB=B[0]-P[0]
    yB=B[1]-P[1]
    xC=C[0]-P[0]
    yC=C[1]-P[1]
    if xA==yA==0 or xB==yB==0 or xC==yC==0:
        return 1
    AB=xA*yB-yA*xB
    AC=xA*yC-yA*xC
    BC=xB*yC-yB*xC
    if AB==0:
        if xA*xB<0 or yA*yB<0:
            return 2
        else:
            return 0
    if AC==0:
        if xA*xC<0 or yA*yC<0:
            return 2
        else:
            return 0
    if BC==0:
        if xB*xC<0 or yB*yC<0:
            return 2
        else:
            return 0
    if AB*BC>0 and AB*AC<0:
        return 3
    return 0

#Sprawdzenie poprawnosci dzialania
A=[0,0]
B=[0,10]
C=[10,0]
P1=[0,5]
P2=[0,15]
P3=[1,1]
P4=[10,10]
print (czywewnatrz(A,B,C,P1))
print (czywewnatrz(A,B,C,P2))
print (czywewnatrz(A,B,C,P3))
print (czywewnatrz(A,B,C,P4))

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)