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)

Zadania do drugiego kolokwium

Zadania, które wspólnie rozwiązaliśmy na zajęciach:

Zadanie 1

Zdefiniuj klasę opisującą wielokąt foremny.

Parametry wejściowe konstruktora obowiązkowe: ilość boków, promień okręgu opisanego na wielokącie.

Metody:

Liniowe powiększenie wielokąta k procent razy.

Narysowanie wielokąta na macierzy obrazu przekazanej jako obowiązkowy parametr, tak by środek wielokąta znajdował się w punkcie przekazanym jako krotka w drugim, nieobowiązkowym parametrze metody. Domyślne położenie środka wielokąta powinno znajdować się na środku obrazu.

Obrót wielokąta o zadany kąt, przekazany jako parametr.

Program:

Wyświetl parę przykładowych wielokątów będących obiektami utworzonej klasy na żółtym tle, wykorzystując moduł cv2.

"""
Created on Thu Jan 18 13:39:01 2018
@author: wszyscy
"""
import cv2
import numpy as np

class wielokat(object):
    
    def __init__(self, n, r):
        self.kat=0
        self.n=n
        self.r=float(r)
    
    def powiekszenie(self, k):
        self.r=self.r*k/100
        
    def rysuj(self, img, s=(-1,-1)):
        if s ==(-1,-1):
            rozmiar=np.shape(img)
            s=(rozmiar[1]/2,rozmiar[0]/2)
        for a in range(self.n):
            x=self.r*np.cos(2*np.pi/self.n*a+self.kat)+s[0]
            y=self.r*np.sin(2*np.pi/self.n*a+self.kat)+s[1]
            x2=self.r*np.cos(2*np.pi/self.n*(a+1)+self.kat)+s[0]
            y2=self.r*np.sin(2*np.pi/self.n*(a+1)+self.kat)+s[1]
            cv2.line(img, (int(x),int(y)),(int(x2),int(y2)), (0,0,1), 1)
        
            
    def obrot(self, kat):         
        self.kat+=kat*np.pi/180
        
try:
    pieciokat=wielokat(n=5,r=50)
    szeciokat=wielokat(6,50)
    img=np.zeros([500,500, 3])+(0,255,255)
    pieciokat.rysuj(img)
    szeciokat.rysuj(img, (50,50))
    pieciokat.obrot(20)
    pieciokat.rysuj(img)
    cv2.imshow("img", img)    
    cv2.waitKey(0)
    
finally:
    cv2.destroyAllWindows()

Zadanie 2

Zdefiniuj klasę opisującą planowane wydatki na najbliższy miesiąc. Każdy wydatek będzie opisywany przez parę: opis wydatku oraz jego wartość.

Parametry wejściowe konstruktora: brak.

Metody:

Dodanie nowego wydatku do budżetu. Parametry obowiązkowe: opis wydatku oraz jego wartość. Jeśli już wcześniej było podane pole o identycznym opisie, jego wartość powinna zostać podmieniona przez nową.

Posortowanie w sposób opisany za pomocą obowiązkowego parametru: alfabetycznie po opisach lub według wartości. Domyślnie sortowanie jest rosnące, chyba że w nieobowiązkowym parametrze zostanie wskazane inaczej.

Zwrot słownika utworzonego z pól budżetu, gdzie kluczami są opisy, a wartościami wielkości wydatków.

Zwrot listy wartosci wydatkow, których opisy zawierają w sobie string przekazany jako nieobowiązkowy parametr metody. Brak parametru oznaczał będzie listy wszystkich wartości wydatków.

Magiczna metoda __str__ wykorzystywana przez funkcję print elegancko wypisująca budżet w kolejności dopisywania lub uwzględniającej ewentualne wcześniejsze posortowanie.

Magiczna metoda __add__ dająca w wyniku budżet utworzony z dwóch innych budżetów. Jeśli opisy wydatku w dwóch budżetach są identyczne, w wyniku powinien znaleźć się tylko jeden wydatek o sumarycznej wartości.

"""
Created on Thu Jan 18 14:42:51 2018
@author: wszyscy
"""

class wydatki(object):
    def __init__(self):
        self.l=[]
        
    def dodaj(self,opis,wartosc):
        for i in range(len(self.l)):
            if opis==self.l[i][0]:
                self.l[i][1]=wartosc
                return
        self.l.append([opis,wartosc])
        
    def sortuj(self,sposob,s=0):
        '''a - alfabetycznie,w - wartosc
        0 - rosnacy, 1 - malejacy'''
        if sposob=='a':
            self.l=sorted(self.l,reverse=s)
        elif sposob=='w':
            self.l=sorted(self.l,key = lambda x:x[1],reverse=s)
            
    def slownik(self):
        return dict(self.l)
        
    def lista(self,s=''):
        l1=[x[1] for x in self.l if s in x[0]]
        l2=[]
        for x in self.l:
            if s in x[0]:
                l2.append(x[1])
        return l1
        
        
    def __str__(self):
        s=''
        for i in self.l:
            s+=i[0]+': '+str(i[1])+'\n'
        return s
        
    def __add__(self,w):
        suma=wydatki()
        for i in self.l:
            suma.dodaj(i[0],i[1])
        for j in w.l:
            k=True
            for x in suma.l:
                if j[0] == x[0]:
                    x[1]+=j[1]
                    k=False
            if k:
                suma.dodaj(j[0],j[1])
        return suma
        
    
budzet=wydatki()
budzet1=wydatki()
budzet.dodaj('praca',100)
budzet.dodaj('praca1',200)
budzet.dodaj('praca1',300)
budzet1.dodaj('praca2',100)
budzet1.dodaj('praca1',200)
budzet3=(budzet+budzet1)