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;
}
}
}
}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.
Pistetään korvan taakse
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öä.
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.
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.)
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.
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ä.
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.
Metabolix kirjoitti:
muista keksiä tehtävään myös matemaattinen ratkaisu
Meinasitko matemaattisella ratkaisulla sitä, että ei käytetä ollenkaan silmukoita?
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.
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?
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?
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.
No mietitäänpäs huomenna
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
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.
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.
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 kirjoitti:
Omassa toteutuksessani on 11 laskutoimitusta.
Kävin koodin läpi ja sain poistettua vielä yhden laskutoimituksen päätyen 10 laskutoimitukseen.
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.
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.
Kun kaavan laskee auki ihan perusmatikalla, sitä voi varmasti sieventää.
Aihe on jo aika vanha, joten et voi enää vastata siihen.