Mainostetaanpa tätä ohjelmointihaastetta myös täällä matikka palstalla:
https://keskustelu.suomi24.fi/t/16695930/kokonaispisteet-kolmiossa
On kuitenkin sen verran matemaattinen tehtävä. Olen itse keksinyt kaksi tehokasta tapaa mutta en vielä postaa niitä. Olisi mukava nähdä paljon erilaisia lähestymistapoja. Ei tarvitse olla niin tehokkaitakaan.
Kokonaispisteet kolmiossa
Anonyymi
21
60
Vastaukset
- Anonyymi
Harvinaisen typerästi muotoiltu alkuperäinen kysymys eikä tämä mainoskaan typeryydessä paljoaakaan jää jälkeen. Mitä kuvittelet tekeväsi? Kolmio? Kokonaispiste?
- Anonyymi
Aivan selkeähän tuo on. Jos hetken vaivaudut miettimään, niin tajuat kyllä miten ne kolmiot tähän liittyvät.
- Anonyymi
Anonyymi kirjoitti:
Aivan selkeähän tuo on. Jos hetken vaivaudut miettimään, niin tajuat kyllä miten ne kolmiot tähän liittyvät.
Taas selittelet. Kokonaisluvuilla laskeminen ei ole yleisessä tapauksessa helppoa. En tiedä millä luokalla olet ja minkä ohjelmointikielen alkeita yrität opetella.
Jos a ja b ovat alle 1000, niin tietysti useimmiten löytyy jaksotus, jolla kombinaatiot saadat laskettua äärellisessä ajassa ihan tulojen summina isoillakin n:n arvoilla. Jos n on alkuluku, niin tulee vaikeuksia sovittaa jaksotusta.
Tyypillinen typerä merkonomitason lasku, jossa rahaa on joitakin triljoonia euroja ja kahta erihintaista tuotetta pitää ostaa mahdollisimman monella eri tavalla ylittämättä budjettia. Ei tuohon löydy kuin yksi toimiva tapa laskea. - Anonyymi
Anonyymi kirjoitti:
Taas selittelet. Kokonaisluvuilla laskeminen ei ole yleisessä tapauksessa helppoa. En tiedä millä luokalla olet ja minkä ohjelmointikielen alkeita yrität opetella.
Jos a ja b ovat alle 1000, niin tietysti useimmiten löytyy jaksotus, jolla kombinaatiot saadat laskettua äärellisessä ajassa ihan tulojen summina isoillakin n:n arvoilla. Jos n on alkuluku, niin tulee vaikeuksia sovittaa jaksotusta.
Tyypillinen typerä merkonomitason lasku, jossa rahaa on joitakin triljoonia euroja ja kahta erihintaista tuotetta pitää ostaa mahdollisimman monella eri tavalla ylittämättä budjettia. Ei tuohon löydy kuin yksi toimiva tapa laskea.En sanonut, että tehtävä on helppo, vaan että tehtävänanto on aivan selkeä, ja että kolmiot kyllä liittyvät asiaan jos vaivaudut hetken miettimään.
Ja kyllä tuohon löytyy erilaisia tapoja ratkaista se. Sekä suhteellisen tehokkaita, että hyvin tehottomia.
Olennaisesti tehtävänä on laskea montako kokonaislukukoordinaateissa sijaitsevaa pistettä on pisteiden 0, n/a ja n/b rajaamaan kolmion sisällä tai reunoilla. - Anonyymi
Anonyymi kirjoitti:
En sanonut, että tehtävä on helppo, vaan että tehtävänanto on aivan selkeä, ja että kolmiot kyllä liittyvät asiaan jos vaivaudut hetken miettimään.
Ja kyllä tuohon löytyy erilaisia tapoja ratkaista se. Sekä suhteellisen tehokkaita, että hyvin tehottomia.
Olennaisesti tehtävänä on laskea montako kokonaislukukoordinaateissa sijaitsevaa pistettä on pisteiden 0, n/a ja n/b rajaamaan kolmion sisällä tai reunoilla.Korjaan: pisteiden (0,0), (n/a,0) ja (0,n/b).
- Anonyymi
Anonyymi kirjoitti:
En sanonut, että tehtävä on helppo, vaan että tehtävänanto on aivan selkeä, ja että kolmiot kyllä liittyvät asiaan jos vaivaudut hetken miettimään.
Ja kyllä tuohon löytyy erilaisia tapoja ratkaista se. Sekä suhteellisen tehokkaita, että hyvin tehottomia.
Olennaisesti tehtävänä on laskea montako kokonaislukukoordinaateissa sijaitsevaa pistettä on pisteiden 0, n/a ja n/b rajaamaan kolmion sisällä tai reunoilla.Et osaa kirjoittaa etkä lukea suomen kieltä. Syytät taas muita osaamattomuudestasi.
Ei laskussa ole mitään ongelmaa kenellekään vähääkään Pythonia osaavalle. Tehoton tapa ei ole edes teoriassa mahdollinen suurilla n:n arvoilla. Laskettava kahdessa osassa. Ensin suurin osa ihan kaavoilla ja sitten se pienen pieni pikkuriikkinen ei suoraan tasan mennyt "yläosa" ohjelmallisesti a ja b pituisilla silmukoilla. Kestää alle sekunnin, vaikka n olisi 10**1000. N. 30 riviä koodia.
Kyse ei ole kolmiosta vaan viisikulmiosta. Eikä senkään nurkka ole origossa.
Eikä tässä yhteydessä voi käyttää "kokonaispiste-" alkuisia termiä. Niissä kyse on ihan muista pisteistä. Katso sanairjasta "piste". Yritit ehkä muodostaa yhdyssanan, jota et osannutkaan kirjoittaa yhteen. - Anonyymi
Anonyymi kirjoitti:
Et osaa kirjoittaa etkä lukea suomen kieltä. Syytät taas muita osaamattomuudestasi.
Ei laskussa ole mitään ongelmaa kenellekään vähääkään Pythonia osaavalle. Tehoton tapa ei ole edes teoriassa mahdollinen suurilla n:n arvoilla. Laskettava kahdessa osassa. Ensin suurin osa ihan kaavoilla ja sitten se pienen pieni pikkuriikkinen ei suoraan tasan mennyt "yläosa" ohjelmallisesti a ja b pituisilla silmukoilla. Kestää alle sekunnin, vaikka n olisi 10**1000. N. 30 riviä koodia.
Kyse ei ole kolmiosta vaan viisikulmiosta. Eikä senkään nurkka ole origossa.
Eikä tässä yhteydessä voi käyttää "kokonaispiste-" alkuisia termiä. Niissä kyse on ihan muista pisteistä. Katso sanairjasta "piste". Yritit ehkä muodostaa yhdyssanan, jota et osannutkaan kirjoittaa yhteen.Ilmeisesti sekoitit minut aloittajaan, joten korjataan nyt sekin: minä en ole kutsunut mitään kokonaispisteiksi. Joka tapauksessa, vaikka tuo termi on epätäsmällinen, asiayhteydestä on päivän selvää mitä sillä aloituksessa tarkoitettiin.
En todellakaan ymmärrä mistä löydät tuohon kuvioon kaksi kulmaa lisää. Ihan esimerkkitapauksena, sovitaan, että a=b=1 ja n=2. Tällöin ne x;y-parit, jotka kelpaavat ratkaisuiksi, ovat 0;0, 0;1, 0;2, 1;0, 1;1 ja 2;0. Jos piirtelet ne koordinaatistoon, niin kuvio näyttää minusta enemmän kolmiolta kuin viisikulmiolta.
PS: Osaan suomea, englantia, (välttävästi) ruotsia, pythonia, C#:ia, C :aa, javaa ja (ruosteisesti) Haskelia. En syytä ketään muuta niistä asioista, joita en osaa. - Anonyymi
Anonyymi kirjoitti:
Et osaa kirjoittaa etkä lukea suomen kieltä. Syytät taas muita osaamattomuudestasi.
Ei laskussa ole mitään ongelmaa kenellekään vähääkään Pythonia osaavalle. Tehoton tapa ei ole edes teoriassa mahdollinen suurilla n:n arvoilla. Laskettava kahdessa osassa. Ensin suurin osa ihan kaavoilla ja sitten se pienen pieni pikkuriikkinen ei suoraan tasan mennyt "yläosa" ohjelmallisesti a ja b pituisilla silmukoilla. Kestää alle sekunnin, vaikka n olisi 10**1000. N. 30 riviä koodia.
Kyse ei ole kolmiosta vaan viisikulmiosta. Eikä senkään nurkka ole origossa.
Eikä tässä yhteydessä voi käyttää "kokonaispiste-" alkuisia termiä. Niissä kyse on ihan muista pisteistä. Katso sanairjasta "piste". Yritit ehkä muodostaa yhdyssanan, jota et osannutkaan kirjoittaa yhteen.Hei! Miten ne a ja b pituiset silmukat menee? Koodin voi laittaa pastebinniin: https://pastebin.pl/ kun näillä sivuilla se on hankala formatoida. Vastausten oli tarkoitus tulla tuonne ohjelmointipalstan puolelle mutta samapa tuo.
- Anonyymi
Anonyymi kirjoitti:
Ilmeisesti sekoitit minut aloittajaan, joten korjataan nyt sekin: minä en ole kutsunut mitään kokonaispisteiksi. Joka tapauksessa, vaikka tuo termi on epätäsmällinen, asiayhteydestä on päivän selvää mitä sillä aloituksessa tarkoitettiin.
En todellakaan ymmärrä mistä löydät tuohon kuvioon kaksi kulmaa lisää. Ihan esimerkkitapauksena, sovitaan, että a=b=1 ja n=2. Tällöin ne x;y-parit, jotka kelpaavat ratkaisuiksi, ovat 0;0, 0;1, 0;2, 1;0, 1;1 ja 2;0. Jos piirtelet ne koordinaatistoon, niin kuvio näyttää minusta enemmän kolmiolta kuin viisikulmiolta.
PS: Osaan suomea, englantia, (välttävästi) ruotsia, pythonia, C#:ia, C :aa, javaa ja (ruosteisesti) Haskelia. En syytä ketään muuta niistä asioista, joita en osaa.Olet hyvä selittelemään. Jos joku huomauttaa sinulle virheistäsi, mikset voi uskoa heitä? Jos x, y>=1, niin sinulle kelpaavat ratkaisuiksi myös (0,0). Ja oikein selitysten kera neuvojaa haukkuen. Selitä miksi! Mitähän oikein yrität laskea?
Monta muutakin asiaa on jäänyt sinulta huomaamatta ja ymmärtämättä jo tässäkin yhteydessä ja varmasti muualla miljoonittain. - Anonyymi
Anonyymi kirjoitti:
Olet hyvä selittelemään. Jos joku huomauttaa sinulle virheistäsi, mikset voi uskoa heitä? Jos x, y>=1, niin sinulle kelpaavat ratkaisuiksi myös (0,0). Ja oikein selitysten kera neuvojaa haukkuen. Selitä miksi! Mitähän oikein yrität laskea?
Monta muutakin asiaa on jäänyt sinulta huomaamatta ja ymmärtämättä jo tässäkin yhteydessä ja varmasti muualla miljoonittain.Rauhoitu, ota vaikka kuppi glögiä ja hengitä.
Näköjään tosiaan tein virheen tuossa alueen rajauksessa, koska olen tottunut aloittamaan indeksoinnin nollasta. Pahoittelut siitä. Se ei kuitenkaan olennaisesti muuta tehtävää mitenkään, koska ratkaisu haetaan täsmälleen samalla logiikalla, riippumatta siitä onko x:n ja y:n alaraja 0, 1, -1 vai 35. Joka tapauksessa tehtävä on selvittää, montako kokonaislukukoordinaateissa sijaitsevaa pistettä on kolmion sisällä tai reunoilla.
Minulle ei ole koskaan ollut ongelma myöntää tekemiäni virheitä. Päin vastoin. Jos minä teen virheen, minä haluan kuulla siitä, että oppisin olemaan tekemättä samaa virhettä jatkossa. Jos siis olet minun kommenteissani huomannut jotain muuta korjattavaa, ole hyvä ja kerro mitä.
- Anonyymi
Tein tällaisen Desmos-appletin: https://www.desmos.com/calculator/omroka0hvo
Siellä yksi brute-force tapa onkin jo näkyvillä (viimeisen rivin s = summa...). Koodit voi laittaa vaikka pastebinniin: https://pastebin.pl/ . - Anonyymi
Pienet luvut saa integroitua Pypyll%C3%A4. Yli 30 kertaa nopeampin kuin Python. %3Cbr %2F%3EJos kokeilee Python 2%3Alla%2C range on korvattava xrangella. Muuten muisti loppuu. %3Cbr %2F%3E%3Cbr %2F%3En %3D 1234567890123%2345%3Cbr %2F%3Ea %3D 883%3Cbr %2F%3Eb %3D 779%3Cbr %2F%3Ec %3D 0%3Cbr %2F%3Efor x in range%281%2Cn%2F%2Fa%2B1%29%3A c %2B%3D %28n-x%2Aa%29%2F%2Fb %3Cbr %2F%3Eprint%28c%29%3Cbr %2F%3E%3Cbr %2F%3E%3Cbr %2F%3EJa kaikki loput luvut saa laskettu jaksoittaisiin s%C3%A4%C3%A4nn%C3%B6llisiin funktioihin soveltuvalla paloittaisintegroinnilla. Riitt%C3%A4%C3%A4 laskea eka viistokattoinen torniosa. Muut aritmeettisella summakaavalla ja lopuksi lis%C3%A4t%C3%A4%C3%A4n vajaajaksoinen loppup%C3%A4tk%C3%A4.%3Cbr %2F%3E%3Cbr %2F%3En %3D 12345678901234%23567890123456789012345678901234567890123456789012345678901234567890%3Cbr %2F%3Eb %3D 779%3Cbr %2F%3Ea %3D 883%3Cbr %2F%3Eab %3D a%2Ab%3Cbr %2F%3Em %3D n - n%AB%3Cbr %2F%3Ep %3D m%2F%2Fab%3Cbr %2F%3Ec %3D 0%3Cbr %2F%3Efor x in range%281%2Cb%2B1%29%3A c %2B%3D %28n-x%2Aa%29%2F%2Fb %3Cbr %2F%3Ecc %3D p%2A%28c-%28p-1%29%2Aab%2Bc%29%2F%2F2 %3Cbr %2F%3Ec %3D 0%3Cbr %2F%3Efor x in range%28m%2F%2Fa%2B1%2Cn%2F%2Fa%2B1%29%3A c %2B%3D %28n-x%2Aa%29%2F%2Fb %3Cbr %2F%3Eprint%28c%29%3Cbr %2F%3Ecc %2B%3D c%3Cbr %2F%3Eprint%28cc%29%3Cbr %2F%3E%3Cbr %2F%3EEi sisennyksi%C3%A4. Toimi suoraan copy-pastella t%C3%A4%C3%A4lt%C3%A4. Laskee mit%C3%A4 vaan paljon alle sekunnissa. Kokeilkaa rajoja. Saa parantaa ihan vapaasti. Jos tied%C3%A4tte jonkun varman tuloksen isolla n%3An arvolla%2C testatkaa ja ilmoittakkaa mahdollisesta virheest%C3%A4. En ole jaksanut tarkistaa ihan kaikkia yli satanumeroisia lukua.
- Anonyymi
Talletus sotki yhden % merkin. Pitää olla:
m = n - n"prosenttimerkki"ab - Anonyymi
Jaksollisuuden ym s%C3%A4%C3%A4nn%C3%B6llisyydet voi todeta ja ymm%C3%A4rt%C3%A4%C3%A4 esim.%3A%3Cbr %2F%3E%3Cbr %2F%3En %3D 1234%3Cbr %2F%3Eb %3D 7%3Cbr %2F%3Ea %3D 8%3Cbr %2F%3Eab %3D a%2Ab%3Cbr %2F%3Em %3D n - n%AB%3Cbr %2F%3Ep %3D m%2F%2Fab%3Cbr %2F%3Ec %3D 0%3Cbr %2F%3Efor i in range%280%2Cp%29%3A %3Cbr %2F%3E__d %3D c%3Cbr %2F%3E__for x in range%28i%2Ab%2B1%2Cb%2Bi%2Ab%2B1%29%3A c %2B%3D %28n-x%2Aa%29%2F%2Fb %3Cbr %2F%3E__print c%2Cc-d%2C%28c-d%29%2F%2Fab%3Cbr %2F%3E%3Cbr %2F%3EToisen sarakkeen arvot pienenev%C3%A4t%2Fkasvavat a%2Ab portain. Niist%C3%A4 muodostuu ekan sarakkeen c-arvon lis%C3%A4ykset.
- Anonyymi
Anonyymi kirjoitti:
Jaksollisuuden ym s%C3%A4%C3%A4nn%C3%B6llisyydet voi todeta ja ymm%C3%A4rt%C3%A4%C3%A4 esim.%3A%3Cbr %2F%3E%3Cbr %2F%3En %3D 1234%3Cbr %2F%3Eb %3D 7%3Cbr %2F%3Ea %3D 8%3Cbr %2F%3Eab %3D a%2Ab%3Cbr %2F%3Em %3D n - n%AB%3Cbr %2F%3Ep %3D m%2F%2Fab%3Cbr %2F%3Ec %3D 0%3Cbr %2F%3Efor i in range%280%2Cp%29%3A %3Cbr %2F%3E__d %3D c%3Cbr %2F%3E__for x in range%28i%2Ab%2B1%2Cb%2Bi%2Ab%2B1%29%3A c %2B%3D %28n-x%2Aa%29%2F%2Fb %3Cbr %2F%3E__print c%2Cc-d%2C%28c-d%29%2F%2Fab%3Cbr %2F%3E%3Cbr %2F%3EToisen sarakkeen arvot pienenev%C3%A4t%2Fkasvavat a%2Ab portain. Niist%C3%A4 muodostuu ekan sarakkeen c-arvon lis%C3%A4ykset.
m = n - n % ab
- Anonyymi
Miten ja millä nimellä tätä ongelmaa on käsitelty matematiikan alkuaikoina? Kuinka monella tapaa voidaan ...?
Löytyykö oeis.org:sta jotain taulukoita? Isoja lukuja on helppo laskea ja tulostaa, mutta miten niitä voi tarkistaa?- Anonyymi
Ongelma on erikoistapaus seuraavasta: https://en.wikipedia.org/wiki/Integer_points_in_convex_polyhedra . Testasin ohjelmaasi ja samoja tuloksia saan myös omillani. Kyllähän se on oikein, jos usealle keskikokoiselle n:lle (jonka voi vielä brute forcellakin testata) tulee oikea tulos :D
Wikipediassa mainittu Ehrhart-polynomi muuten liittyy minun toiseen algoritmiin. Tai siinä taitaa tulla se kvasi-tapaus, sillä kolmion kärjet eivät välttämättä ole kokonaislukupisteissä. Noh, minä selostan sitten sen "tapauskohtaisen polynomisuuden" jos nyt postaisin ne omat algoritmini tuonne alle.
- Anonyymi
REKURSIIVINEN ALGORITMI
Ensimmäinen algoritmini tekee seuraavaa. Jaetaan kolmio suorakaiteeseen ja kahteen pienempään kolmioon. Ks kuva: https://www.desmos.com/calculator/aiktou2el9 . Suorakaide on helppo laskea ja pienemmät kolmiot ovat pienempiä tapauksia samasta ongelmasta. Rekursoidaan.
Koodi: https://pastebin.pl/view/465f20ed- Anonyymi
Ai niin ja memoisaatio tarvitaan myös, muuten ei tule nopea. Pienet tapaukset lasketaan brute force metodilla. Jos a ja b ovat hyvin suuria, niin ne "pienet" tapauksetkin saattavat vielä olla merkittävän kokoisia.
- Anonyymi
POLYNOMI ALGORITMI
Ongelma voidaan ilmaista myös näin: Kuinka monta ei-negatiivista ratkaisua on yhtälöllä
ax by z = n
Tämä johtuu siitä, että uusi muuttuja z voi juosta 0:sta n:ään, joten ax by voi olla mitä tahansa n:stä 0:llaan. (Sallitaankin siis myös arvo nolla muuttujille; niiden ratkaisujen lukumäärä voidaan lopuksi vähentää). Muuttuja z siis hoitaa summauksen. Sitä taidetaan enkuksi kutsua slack-variable, joka muuttaa epäyhtälön yhtälöksi.
Merkitään P0(n) yhtälön z=n epänegatiivisten ratkaisujen määrää (eli tietenkin vakio 1). Vastaavasti P1(n) olkoon yhtälön by z = n epäneg ratkaisujen määrä ja P2(n) yhtälön ax by z = n.
P0 jo edellä "ratkaistiinkin". Ratkaistaan nyt P1. Se saadaan summana P0:n arvoista pisteissä n-by, kun y juoksee sallituissa rajoissa ja laskenta siten jakautuu b:hen eri tapaukseen riippuen siitä mitä n on modulo b. Jokainen näistä on lineaarinen polynomi n:n suhteen.
Sitten P2:n ratkaisemisessa vastaavasti summataan P0:n arvoja ja jakaudutaan edelleen a:han eri tapaukseen riippuen n:n arvosta mod a.
Kaiken kaikkiaan kuitenkin huomataan, että vastaus on jokin toisen asteen polynomi (riippuen siis n:stä modulo ab (tai oikeastaan lcm(a,b))). Noh, minä en viitsinyt lähteä laskeskelemaan sitä noilla summauksilla, vaan ratkaistaan se lagrangen interpolaatiopolynomina kun tiedetään arvo kolmessa pisteessä. Nämä kolme ja ne voi laskea vaikka brute forcella. Mutta koska arvojen täytyy olla samaa kuin n modulo ab (koska sama polynomi toimii vain samalle jäännösluokalle), niin taas jos a ja b ovat suuria, voi laskenta olla hidasta.
Koodi (Sagea): https://pastebin.pl/view/90e18a1d- Anonyymi
Ai niin: se nollan sisältävien ratkaisujen määrän vähäntäminen ei muuta sitä tosiasiaa, että ratkaisu on polynomi.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Epäily: Oppilas puukotti kolmea Pirkkalan koululla
Tämänhetkisen tiedon mukaan ainakin kolme oppilasta on loukkaantunut puukotuksessa Pirkkalan Vähäjärven koululla. Myös e3178123Jos yhdistät nimikirjaimet
Jos yhdistät sinun ja kaivattusi ensimmäisten nimien alkukirjaimet mitkä nimikirjaimet tulee? Sinun ensin ja sitten häne996369Jos olisit täällä
Tosin en tiiä miks oisit. (Ja hävettää muutenkin kun ei muka muulla tavoin osaa kertoa tätäkään) Jos jollain pienellä1743673- 702440
Kyllä se taitaa olla nyt näin
Minusta tuntuu et joku lyö nyt kapuloita rattaisiin että meidän välit menisi lopullisesti. Sinä halusit että tämä menee402430- 422204
Odotan että sanot
Sitten siinä että haluaisit vielä jutella kahdestaan kanssani ja sitten kerrot hellästi että sinulla on ollut vaikea san222176Pirkkalan koulussa puukotus, oppilas puukotti kolmea
Ilmeisesti tyttöjä ollut kohteena.1962014- 831877
- 481575