Kirjautuminen

Haku

Tehtävät

Keskustelu: Ohjelmointiongelmat: C#: Ratsujen asettelu shakkilaudalle

Sivu 1 / 1

Sivun loppuun

AtskaFin [20.02.2019 20:26:06]

Lainaa #

Harjoittelen koodaamista cses.fi/dt/list/ sivun tehtävillä. Teen tehtävää http://cses.fi/dt/task/320 (monellako tavalla n×n-shakkilaudalle voi sijoittaa kaksi ratsua niin, että ne eivät uhkaa toisiaan). En tiedä miten surkeaa koodia tämä on, mutta en vain saa toimimaan (katson toimimisen siis sillä esimerkillä mikä tehtävässä on annettu) voisitteko antaa vinkin (ei koodia), mikä menee vikaan.

using System;

namespace csesHarjoitukset
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int mahdollisuudet = 0;

            //ratsu 1:n liikkuminen
            for (int ekaRatsuX = 1; ekaRatsuX <= n; ekaRatsuX++)
            {
                for (int ekaRatsuY = 1; ekaRatsuY <= n; ekaRatsuY++)
                {
                    //ratsu 2:n liikkuminen
                    for (int tokaRatsuX = 1; tokaRatsuX <= n; tokaRatsuX++)
                    {
                        for (int tokaRatsuY = 1; tokaRatsuY <= n; tokaRatsuY++)
                        {
                            if(ekaRatsuX == tokaRatsuX && ekaRatsuY == tokaRatsuY)
                            {
                                //Ei ole mahdollista olla samassa paikassa
                            }
                            //Jos metodi cantEat palauttaa True, niin mahdollisuuksia on yksi enemmän
                            else if(cantEat(ekaRatsuX, ekaRatsuY, tokaRatsuX, tokaRatsuY))
                            {
                                mahdollisuudet++;
                            }
                        }
                    }
                }
            }

            Console.WriteLine(mahdollisuudet);
        }

        //Palauttaa true, jos syöminen ei ole mahdollista
        static Boolean cantEat(int ekaX, int ekaY, int tokaX, int tokaY)
        {
            //Eka ratsu siiryy oikealle
            if(ekaX + 2 == tokaX && ekaY + 1 == tokaY || ekaX + 2 == tokaX && ekaY - 1 == tokaY)
            {
                return false;
            }
            //Eka ratsu siirtyy vasemmalle
            else if (ekaX - 2 == tokaX && ekaY + 1 == tokaY || ekaX - 2 == tokaX && ekaY - 1 == tokaY)
            {
                return false;
            }
            //Eka ratsu siirtyy ylös
            else if (ekaY + 2 == tokaY && ekaX + 1 == tokaX || ekaY + 2 == tokaY && ekaX - 1 == tokaX)
            {
                return false;
            }
            //Eka ratsu siirtyy alas
            else if (ekaY - 2 == tokaY && ekaX + 1 == tokaX || ekaY - 2 == tokaY && ekaX - 1 == tokaX)
            {
                return false;
            }
            //Ei voi syödä, palauttaa true
            else
            {
                return true;
            }
        }
    }
}

Metabolix [20.02.2019 21:20:19]

Lainaa #

Kokeilet kaikkia sijainteja molemmille ratsuille, joten lasket jokaisen ruutuparin kahteen kertaan: vaihtoehdon 1-2 ja vaihtoehdon 2-1. Tehtävässä ratsujen järjestyksellä ei ole merkitystä, joten voit jakaa tuloksen kahdella tai korjata silmukoiden ehtoja niin, että ensimmäinen ratsu on aina joko ylemmällä rivillä tai saman rivin pienemmissä koordinaateissa.

Yleensäkin tällaisissa tehtävissä on hyvä myös lukuarvon puolesta verrata omaa vastausta ja oikeaa vastausta ja katsoa, löytyykö jokin looginen yhteys. Esimerkiksi tässä tapauksessa on helppo todeta, että lukujen suhde on 1:2. Lisäksi voi laskea pieniä tapauksia käsin, esimerkiksi 3x3-laudan sijoittelut on helppo vaikka piirtää paperille.

AtskaFin [21.02.2019 08:33:51]

Lainaa #

Pistetään korvan taakse

Metabolix [21.02.2019 11:28:13]

Lainaa #

Ai niin: muista keksiä tehtävään myös matemaattinen ratkaisu. Tuolla koodilla esim. tapaus 1000 on jo liian hidas, ja tulos ei edes mahdu int-muuttujaan vaan edellyttää long-tyypin käyttöä.

jalski [23.02.2019 10:03:51]

Lainaa #

Metabolix kirjoitti:

Ai niin: muista keksiä tehtävään myös matemaattinen ratkaisu. Tuolla koodilla esim. tapaus 1000 on jo liian hidas, ja tulos ei edes mahdu int-muuttujaan vaan edellyttää long-tyypin käyttöä.

Bonuksena matemaattisella ratkaisulla pääsisi helposti sivuston https://cses.fi/dt/stats/320/ statistiikan viiden nopeimman koodin listan kärkeen 0.00 sekunnin suoritusajalla.


Kokeilin tehtävää 8th:lla ja sain tulokseksi:

C:\temp>8th knights.8th
Anna koko n, n x n laudalle:
8
Tulos: 1848 mahdollisuutta.
Aikaa meni 0.00135 sekunttia.

Metabolix [23.02.2019 11:46:45]

Lainaa #

jalski: Järjestelmässä näyttää olevan jotain hukkaa ja hieman satunnaista vaihtelua, minkä vuoksi jopa tyhjän ohjelman suoritus vie 0,01–0,03 sekuntia. Listan kärkeen on siis hyvin epätodennäköistä päästä. (Ajattelitko, että jollain muullakin ratkaisulla voisi päästä tuohon listalla olevaan 0,02 sekunnin aikaan tapauksessa n = 1000? Silmukat vievät väistämättä paljon pidempään.)

jalski [23.02.2019 14:28:02]

Lainaa #

Metabolix kirjoitti:

jalski: Järjestelmässä näyttää olevan jotain hukkaa ja hieman satunnaista vaihtelua, minkä vuoksi jopa tyhjän ohjelman suoritus vie 0,01–0,03 sekuntia. Listan kärkeen on siis hyvin epätodennäköistä päästä.

En huomioinut järjestelmän hukkaa ja satunnaista vaihtelua vaan otin jonkinlaisen ajastusarvion suoraan koodissa.

jalski [23.02.2019 17:55:27]

Lainaa #

Kokeilin vielä piruuttani ajastaa ohjelman suorituksen käyttämällä Windows PowerShell:in Measure-Command apuohjelmaa. Tulos oli 8th:n tapauksessa 55 millisekuntia, eli kärkipaikkaan sillä ei päästäisi. Tein vielä ohjelmasta PL/I käännöksen ja suoritin sille saman testin. PL/I:llä fixed decimal tietotyyppiä käytettäessä ohjelman suoritusaika oli 10 millisekuntia, jolla jo mentäisiin listan kärkeen.

Alla PL/I versio: Mod. huom: Ei nyt spoilata harjoitustehtävän ratkaisua selkokielisenä.

Metabolix [23.02.2019 20:05:52]

Lainaa #

jalski kirjoitti:

jolla jo mentäisiin listan kärkeen.

Kuten jo kerran selitin, listan kärkeen ei mennä edes nollan sekunnin ohjelmalla, koska tuo järjestelmä tuottaa mittauksiin 0,01–0,03 sekuntia ylimääräistä. Oma C-ohjelmani vie 0–3 millisekuntia (tässä tulee jo käyttöjärjestelmän puolesta jotain vaihtelua), ja silti CSES-sivusto antaa sille vaihtelevasti 0,01–0,03 sekunnin aikoja.

AtskaFin [23.02.2019 22:48:04]

Lainaa #

Metabolix kirjoitti:

muista keksiä tehtävään myös matemaattinen ratkaisu

Meinasitko matemaattisella ratkaisulla sitä, että ei käytetä ollenkaan silmukoita?

L2-K2 [23.02.2019 23:17:08]

Lainaa #

AtskaFin kirjoitti:

Metabolix kirjoitti:

muista keksiä tehtävään myös matemaattinen ratkaisu

Meinasitko matemaattisella ratkaisulla sitä, että ei käytetä ollenkaan silmukoita?

Sitä tuo tosiaan taitaa tässä tapauksessa tarkoittaa.

Tuo yksinkertainen silmukkaratkaisu tarvitsee neljä silmukkaa ja siten tässä noin pyöreästi luokkaa ”n^4 = n × n × n × n” laskutoimitusta (missä n on laudan sivun mitta). Hieman tehokkaamman algoritmin taitaa tässä saada tehtyä kahdella silmukalla (jos yli vuosikymmenen takaa tehtävän hieman vaikeammasta versiosta* oikein muistan), eli noin ”n^2 = n × n” operaatiota. Mutta, tuon oikean yhdistelmien määrän saa tosiaan laskettua (verrattain) yksinkertaisella kaavalla vakioajassa, eli ”1” operaatio riippumatta laudan koosta.

Yksi on lainausmerkeissä, koska tuo kaava tarvinnee sen noin puolen tusinaa alkeisoperaatiota (mutta ne tasan samat operaatiot tehdään oli laudan sivun pituus 4 tai 4000).

* Vaikeampi versio: kolme hevosta laudalle: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=kunhev . Tälle tuo yksinkertaisin ratkaisu on tietenkin kolmella hevosella kuuden silmukan ”n^6” -ratkaisu. Välimallina löytynee ainakin neljän silmukan ”n^4” -ratkaisu ja olettaisin myös että kolmen silmukan ”n^3” -ratkaisu, ja sitten myös tälle ei-ihan-niin-yksinkertaisesti myös tuo vakioaikainen ratkaisu (laskukaava, eli vain yksi laskuoperaatio riippumatta laudan koosta). Tuon laskuoperaation laskenta-aika toki kasvaa sitten kun se yhdistelmien määrä ei enää mahdu vaikkapa siihen 64-bittiseen kokonaislukumuuttujaan.

Metabolix [24.02.2019 20:56:45]

Lainaa #

Mieti asiaa vaikka askel kerrallaan vaikeutuen: Osaatko tehdä ilman silmukoita kaavan, joka laskee, monellako tavalla yksi nappula voidaan laittaa n×n-ruudukkoon? (Toivottavasti osaat!) Entä kaksi nappulaa ilman uhkaussääntöjä? Entä kaksi tornia niin, että ne eivät uhkaa toisiaan? Entä kaksi lähettiä? Entä lopulta nämä kaksi ratsua?

AtskaFin [26.02.2019 21:13:27]

Lainaa #

Olen tässä tunteroisen pähkäillyt ja keksinyt seuraavaa:

monellako tavalla yksi nappula voidaan laittaa n×n-ruudukkoon?
n x n

kaksi nappulaa ilman uhkaussääntöjä?
(n x n - 1) x n x n / 2

Menikö tuo toinen oikein?

Metabolix [26.02.2019 21:25:48]

Lainaa #

Oikein meni tähän asti. (Kaksi nappulaa: n×n paikkaa ensimmäiselle nappulalle, n×n-1 paikkaa toiselle, ja jako kahdella, koska nappuloiden järjestyksellä ei ole merkitystä.)

Torni on myös helppo, koska se uhkaa yhtä monta ruutua sijainnista riippumatta. Lähetin ja ratsun kohdalla lasku vaikeutuu, koska estettyjä ruutuja on eri määrä eri kohdassa (esim. lähetillä nurkassa vain n mutta keskellä lautaa enintään 2n-1). Itse asiassa lähetit ja ratsut taitavat olla suunnilleen yhtä vaikeita ratkaista. Ehkä lähettien sijaan voisi laskea kaksi kuningasta.

AtskaFin [26.02.2019 22:05:21]

Lainaa #

No mietitäänpäs huomenna

AtskaFin [11.06.2019 22:44:12]

Lainaa #

Olin unohtanut koko tehtävän, mutta nyt illan aikana sain matemaattisen laskutoimituksen kasaan. Voitteko sanoa meneekö nämä oikein?

Anna n: 8
Mahdollisuuksia: 1848

Anna n: 178
Mahdollisuuksia: 501797478

Anna n: 8539
Mahdollisuuksia: 2658263358316836

Anna n: 178344
Mahdollisuuksia: 505829339805246160000

jalski [11.06.2019 23:11:21]

Lainaa #

AtskaFin kirjoitti:

(11.06.2019 22:44:12): Olin unohtanut koko tehtävän, mutta nyt illan...

Viimeinen on väärin, vastauksen pitäisi olla: 505829339805246128056. Muut ovat oikein, eli todennäköisesti kaavasi on oikein, mutta käyttämäsi tietotyyppi ei pysty laskemaan noin isoilla numeroilla.

AtskaFin [11.06.2019 23:18:18]

Lainaa #

Käytin kielenä javascriptiä. Se taitaakin laskea vain 15 numeron tarkkuudella, mitä ainakin netistä luin.

Tuli muuten todella sekava kaava. Siinä on semmoset 37 laskutoimitusta.

jalski [12.06.2019 10:24:22]

Lainaa #

AtskaFin kirjoitti:

Tuli muuten todella sekava kaava. Siinä on semmoset 37 laskutoimitusta.

Tuollaiset 37 laskutoimitusta Kuulostaa aika paljolta tähän tehtävään!

Omassa toteutuksessani on 11 laskutoimitusta.

jalski [12.06.2019 17:11:09]

Lainaa #

jalski kirjoitti:

Omassa toteutuksessani on 11 laskutoimitusta.

Kävin koodin läpi ja sain poistettua vielä yhden laskutoimituksen päätyen 10 laskutoimitukseen.

AtskaFin [12.06.2019 20:08:13]

Lainaa #

Miten lausekkeesta niin lyhyen saa? Hevosethan uhkaavat eri määriä sijainnista riippuen ja laudan koosta riippuen on eri määrä kohtia josta vaikka uhkaa kolmea paikkaa.

jalski [12.06.2019 20:30:15]

Lainaa #

AtskaFin kirjoitti:

Miten lausekkeesta niin lyhyen saa? Hevosethan uhkaavat eri määriä sijainnista riippuen ja laudan koosta riippuen on eri määrä kohtia josta vaikka uhkaa kolmea paikkaa.

Yksitoista laskutoimitusta vaadittaisiin, mutta yhden laskutoimituksen saa siitä pois koska yksi sama kertolasku tehdään kaksi kertaa.

Metabolix [13.06.2019 18:07:47]

Lainaa #

Kun kaavan laskee auki ihan perusmatikalla, sitä voi varmasti sieventää.


Sivun alkuun

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta