Rakstīt ziņojumu 
 
Pavediena vērtējums:
  • 0 balsis - 0 vidējais
  • 1
  • 2
  • 3
  • 4
  • 5
uzdevums _ algoritms
Autors Ziņa
nothin Atslēdzies
Member
***

Ziņojumi: 60
Pievienojās: May 2010
Reputācija: 2
Ziņojums: #1
uzdevums _ algoritms
Sveiki!
Man ir sekojošs uzdevums (tas nav mācībām), iesakiet kādu iedeju labam algoritmam:

- ir 30 vai 31 kaste, kas stāv viena blakus otrai vienā rindā
- ir 3 veidu bumbiņas (zilas, zaļas, sarkanas)
- katrā kastē ir jāliek tieši 2 bumbiņas
- zilo, zaļo un sarkano bumbu kastēš ir jāieliek vienādā skaitā (plus/mīnus 1 - atkarībā no tā, cik kastes ir dotas)

Ir jāpanāk tāds bumbiņu izvietojums kastē, lai maksimāli iespējami izpildītos sekojošas prasības:

a) visoptimālākais izvietojums katrai bumbiņai ir "4+2" vai "3+2" (kas nozīmētu, piemēram, ka 4 kastes blakus ir ar sarkano bumbiņu un tad 2 kastes nav ar sarkano bumbiņu); ja to nav iespējams panākt, tad jebkurā gadījumā vienas krāsas bumbiņas nedrīkst atrasties 5ās kastēs blakus;

b) katrai bumbiņai ir iespējams norādīt līdz 2 kastes numuriem, kuros tā noteikti nedrīkst būt (piemēram, sarkanā bumbiņa nedrīkst būt kastē nr.1 un kastē nr.4) - šī prasība ir primārāka par prasību a).


Programmai jārisina šis uzdevums pēc iespējas optimālāk (tas nozīmētu, ka risinājumam jābūt gana labam gana bieži... vai kkā tā).

Manas idejas:
- sākumā ignorē b punktu un sameta bumbiņas kastēs 4+2 variantā; tad mēģina ieviest punktu b, kaut kā mainot bumbiņas (nezinu kā)

- bez maz vai pilnā pārlase ar kaut kādām heuristikām (ņemot teiksim punktu b vērā)

Nekas prātīgs nenāk prātā.
15.12.2010 23:53
Atrast visus šī lietotāja rakstītos ziņojumus Citēt šo ziņu atbildē
Neps Atslēdzies
Junior Member
**

Ziņojumi: 1
Pievienojās: Dec 2010
Reputācija: 0
Ziņojums: #2
RE: uzdevums _ algoritms
nezinu vai tev tas derees, bet man kautkaa shitaa sanaaca

<?php
$boxes="<html><head></head><body><table cellspacing=2 cellpadding=0 border=2><tr>";
for ($i=1;$i<32;$i++){
$boxes.="<td id=\"box$i\" style=\"height: 50px;\" valign=top>Box$i<br></td>";

}
$boxes.="</tr></table>
<script type=\"text/javascript\">
function addRedball(id){
document.getElementById(id).innerHTML+=\"<span style='color: red;'>*</span>\";
}
function addBlueball(id){
document.getElementById(id).innerHTML+=\"<span style='color: blue;'>*</span>\";
}
function addGreenball(id){
document.getElementById(id).innerHTML+=\"<span style='color: green;'>*</span>\";
}
var box=new Array();
var j=0;
for (i=1;i<32;i++){
var idf=\"box\"+i;
if (((i-1)/2)==Math.ceil((i-1)/2)){
j++;
}
if (j==0){
addRedball(idf);
addBlueball(idf);
}
if (j==1){
addGreenball(idf);
addBlueball(idf);
}
if (j==2){
addGreenball(idf);
addRedball(idf);
}
if (j==3){
addRedball(idf);
addBlueball(idf);
j=0;
}
}
</script>
</body></html>
";
echo $boxes;
?>
19.12.2010 10:16
Atrast visus šī lietotāja rakstītos ziņojumus Citēt šo ziņu atbildē
Ēriks Klotiņš Atslēdzies
Senior Member
****

Ziņojumi: 428
Pievienojās: May 2005
Reputācija: 4
Ziņojums: #3
RE: uzdevums _ algoritms
Uzdevuma formulējumā nav minēts bumbiņu sākuma stāvoklis.
Ir pieejams kaut kāds steks ar sajauktām visu 3 krāsu bumbinām?
Ir pieejami 3 steki ar katras krāsas bumbinām?

Bez tam ar "optimāls risinājums" parasti saprot pēc iespējas mazāku O(n)
19.12.2010 21:12
Atrast visus šī lietotāja rakstītos ziņojumus Citēt šo ziņu atbildē
ulzha Atslēdzies
Koto Member
****

Ziņojumi: 683
Pievienojās: May 2006
Reputācija: 16
Ziņojums: #4
RE: uzdevums _ algoritms
Nav nozīmes sākuma stāvoklim. Ja ir 30 kastes, tad tev ir 20 katrā krāsā, un tās vnk jāliek

Tiek meklēts optimums kaut kādā iegūstamā izkārtojuma skaistuma ziņā, nevis efektivitātes. 3 medmāsu darba grafiks mēnesī vai? Smile

Man gribētos sākt ar (zila+zaļa, zila+zaļa, zaļa+sarkana, zaļa+sarkana, sarkana+zila, sarkana+zila)* - tas ir tas "4 strādā un 2 brīvas" - un tad kaut kā pārkārtot, lai atbilst (b)...
19.12.2010 21:44
Atrast visus šī lietotāja rakstītos ziņojumus Citēt šo ziņu atbildē
Rakstīt ziņojumu 


Lēciens uz forumu:



Kontaktifizmati.lvAtgriezties uz augšuAtgriezties pie saturaArhīva skatsRSS sindikācija