Programmering - maraton

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Viser til tidlegare ulikheit-maraton. Dette "løpet" gjekk over fleire månader før interessa slokna.
Inviterer hermed til eit tilsvarande løp i programmering.
Startar " kronerullinga" med å presentere dette problemet:
Lag eit dataprogram i Python-kode som plukkar ut og skriv ut alle primtal mindre enn 100.

Programvare: https://trinket.io/python3
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Fint tiltak! Jeg hiver meg på.

Primtallsarbeid er løselig på mange måter, men jeg går for en forholdsvis enkel en. Jeg lager en funksjon som tar et heltall og sjekker at ingen tall under det, deler det.

Det finnes gradvis mindre naive måter å gjøre det på.

For $n$, sjekk at $2, 3, 4, \ldots, n-1$ ikke deler det. Dette er den enkleste å skrive, men vi sjekker veldig mange tall som ikke har mulighet til å dele $n$. Eksempelvis sjekker vi tall som er større enn $\frac n2$.

Vi kan begrense søket til tall mindre enn $\sqrt n$, siden hvis vi ikke har funnet noen faktorer før det, så vil vi heller ikke finne par-faktoren som må være større.

Videre vil vi helst ikke sjekke alle partall. Så fort vi har sjekket at 2 ikke deler $n$, så vet vi at ingen andre partall deler $n$ heller. Så vi sjekker i stedet $3, 5, 7, \ldots$.

Det finnes enda bedre måter. For eksempel, hvis 3 ikke er en faktor, så er heller ikke $9, 15, 21 \ldots$ faktorer. Men det er her jeg velger å gå for lettvint kode fremfor maksimal optimalisering. Dersom måltallet ikke hadde vært 100, men $10^{10}$ så hadde jeg nok valgt annerledes.

Kode: Velg alt

import math


def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  for i in range(3, math.ceil(math.sqrt(n) + 1), 2):
    if n % i == 0:
        return False
  return True


print([n for n in range(2, 100) if isPrime(n)])

Oppfølger: Finn summen av arealene til sirklene med radius $1, 2, 3, \ldots, 100$. Avrund svaret til nærmeste heltall.
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Problem: Lage eit dataprogram i Python-kode som reknar ut summen av areala til alle sirklar med radius f.o.m. r = 1 t.o.m. r = 100

Dette er eit relativt greitt problem utan vilkårtest ( ingen if-setningar ). Lagar ei FOR-løkke og summerer:

1) areal = 0 ; sum = 0 ; pi = 3.14
2) for i in range(1 , 101 ):
3) sum = sum + i*i
4) areal = sum * pi
5) print( " Samla areal: " , round(areal ) )

P.S. Greidde ikkje å kopiere programmet eg køyrde på PC-en. Skriv difor instruksjonane " for hand".

Oppfølgar: Legge inn n tal( element) i ei liste og sortere desse etter stigande verdi.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Mattebruker skrev: 21/05-2022 21:45 Problem: Lage eit dataprogram i Python-kode som reknar ut summen av areala til alle sirklar med radius f.o.m. r = 1 t.o.m. r = 100

Dette er eit relativt greitt problem utan vilkårtest ( ingen if-setningar ). Lagar ei FOR-løkke og summerer:

1) areal = 0 ; sum = 0 ; pi = 3.14
2) for i in range(1 , 101 ):
3) sum = sum + i*i
4) areal = sum * pi
5) print( " Samla areal: " , round(areal ) )
Når jeg kjører dette så får jeg verdien $1062419$ men det egentlige svaret er $1062958$.

Feilen er funnet, men feilsøking er en enormt viktig del av det å skrive kode, så du må få sjansen til å rette det opp :)
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Kanskje ligg feilen her ? pi = 3.141592654 ( 9 siffer bak desimalkomma )
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Det stemmer. En avrundingsfeil så tidlig i utregninga får en eksplosiv effekt når vi multipliserer det med så store tall som her.

Python har et innebygd "math"-bibliotek som blant annet har diverse viktige konstanter tilgjengelig.

Kode: Velg alt

from math import pi
lar deg hente denne, og deretter bare bruke "pi" som du får derfra.
Bilde
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Mattebruker skrev: 21/05-2022 21:45 Oppfølgar: Legge inn n tal( element) i ei liste og sortere desse etter stigande verdi.
Fortsetter her.

Jeg husker fremdeles den første sorteringsalgoritmen jeg laga selv, før jeg lærte om andre, mer effektive sorteringsalgoritmer. Det var veldig naiv, men lett å forstå.

Kode: Velg alt

from random import randint

# Instansierer ei liste med 2000 vilkårlige heltallsverdier
list = [0] * 2000
for i in range(0, len(list)):
    list[i] = randint(0, 1000)

# Definerer en funksjon som sjekker om ei liste er sortert
def is_sorted(list):
    for i in range(0, len(list)-1):
        if list[i] > list[i+1]:
            return False
    return True


# Definerer en funksjon som kjører gjennom lista og bytter plass
# på påfølgende verdier dersom den første er større enn den andre
def run(list):
    for i in range(0, len(list)-1):
        first = list[i]
        second = list[i+1]
        if first > second:
            list[i] = second
            list[i+1] = first
    return list


# Så lenge lista ikke er sortert, kjør prosessen som bytter elementer
while not is_sorted(list):
    list = run(list)


print(list)
Ikke en algoritme jeg ville brukt på lister med millioner av elementer eller mer, men fungerer fint til under en million.

Oppfølger: Finn summen av de første 1000 Fibonacci-tallene. La tallfølgen starte med $1, \ \ 1, \ \ 2$.
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Summen av dei 1000 første Fibonaccitala( Python-kode )
1 liste = [0]* 1000
2 liste[1] = 1 ; liste[2] = 1; sum = 2
3 for i in range(3 , 1000):
4 liste[ i ] = liste[ i -1] + liste[ i - 2 ]
5 sum = sum + liste[ i ]
6 print(" Summen av dei 1000 første Fibonaccitala: " , sum )

Kommentar: Eit svimlande stort tal! Bør presenterast på standardform for at "output" skal ha informativ verdi.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Mattebruker skrev: 17/07-2022 22:21 Summen av dei 1000 første Fibonaccitala( Python-kode )
1 liste = [0]* 1000
2 liste[1] = 1 ; liste[2] = 1; sum = 2
3 for i in range(3 , 1000):
4 liste[ i ] = liste[ i -1] + liste[ i - 2 ]
5 sum = sum + liste[ i ]
6 print(" Summen av dei 1000 første Fibonaccitala: " , sum )

Kommentar: Eit svimlande stort tal! Bør presenterast på standardform for at "output" skal ha informativ verdi.
Kanskje ikke en veldig gjennomtenkt oppgave fra min side med tanke på størrelsen på svaret.

Justering: Finn de tre siste sifrene i summen av de 1000 første Fibonacci-tallene. :)
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Lat n vere eit naturleg tal med mange siffer. Da skal denne kommandoen plukke ut dei tre siste siffera:

tresiste = n - round((n - 500)/1000)*1000
Fungerer når n har rimeleg mange siffer , eks. n = 6729451879, men greier ikkje handtere summen av dei 1000 første fibonacci-tala.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Vi kan finne de tre siste sifrene ved å redusere svaret modulo 1000.

Python har en innebygd funksjon for moduloregning, som bare bruker prosenttegn.

For eksempel vet vi at $7 \equiv 2 \pmod 5$. Med Python kunne vi funnet dette ved å bare skrive "print(7 % 5)" som ville gitt svaret $2$.

Hvis vi gjenbruker din løsning for Fibonacci, men reduserer summen modulo 1000 til slutt:

Kode: Velg alt

liste = [0] * 1000
liste[1] = 1
liste[2] = 1
sum = 2
for i in range(3, 1000):
    liste[i] = liste[i - 1] + liste[i - 2]
    sum = sum + liste[i]
tre_siste_siffer = sum % 1000

print(tre_siste_siffer)
Som gir $500$.
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Aleks: " Python har en innebygd funksjon for moduloregning"
Smart løysing! Var ikkje merksam på denne funksjonen.

Oppfølgar ( maybe a challenge problem ):

Skriv eit program som tek inn eit heiltal frå brukar. Programmet skal så sjekke om talet inneheld sifferet 7 og skrive ut resultatet.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Mattebruker skrev: 19/07-2022 10:38
Skriv eit program som tek inn eit heiltal frå brukar. Programmet skal så sjekke om talet inneheld sifferet 7 og skrive ut resultatet.

Kode: Velg alt

def p(n): return 7 in [int(a) for a in str(n)]

Oppfølger: Skriv et program som tar som input et heltall N>1, og returnerer summen av de første N primtall som ikke inneholder sifre som er odde primtall.
Mattebruker
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 26/02-2021 21:28

Vedr. Gustav sin oppfølgar:

Har laga eit program slik innsendar bed om. No er eg spent på om eg har tolka problemet rett.

Eksempel: Input N = 10 gir denne talrekkja: 29 - 89 - 229 - 269 - 409 - 449 - 499 - 809 - 829 - 929 ( sum = 4540 )
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Mattebruker skrev: 27/07-2022 08:13 Vedr. Gustav sin oppfølgar:

Har laga eit program slik innsendar bed om. No er eg spent på om eg har tolka problemet rett.

Eksempel: Input N = 10 gir denne talrekkja: 29 - 89 - 229 - 269 - 409 - 449 - 499 - 809 - 829 - 929 ( sum = 4540 )
2 er et primtall som ikke inneholder odde primsifre, så det må også med. I tillegg er 1 ikke primtall, så tall som 11 og 19 må også være med.
Svar