Դիտել ողջ տարբերակը : Կշռումներ
Նախորդ իմ կշռաքարերի խնդիրը արժանացավ ընդամենը մեկ հոգու պատասխանի, այն էլ սխալ: Անկեղծ ասած ես սպասում էի ավելին: Ինչեվիցե միհատ էլ խնդիր, այս
անգամ գրաֆների տեսությունից: Այն անվանում են մինիմալ կմախքային ծառ գտնելու խնդիր:
Նախ ընդանուր խնդրի դրվացքը:
Ունենք n հատ քաղաք որոնք միցված են իրար
որոշակի ճանապարհներով: Ոչ մի քաղաք մեկուսացված չի մնացածից՝ այսինքն
ցանկացած երկու քաղաք միացված են ճանապարհով ,որը , միգուց է , անցնում է
մեկ այլ քաղաքով կամ քաղաքներով : Այդ ճանապարհներից ոչ մեկը ասֆալտապատաց չէ: Պահանջում է ասֆալտապատել այնպիսի մինիմալ՝ նվացագույն ծախսեր ունեցող ճանապարհ , որը անցնի բոլոր քաղաքներով:
Հիմա գրաֆների լեզվով:
Տրված է կապակցված գրաֆ:Գրաֆի յուրաքանչյուր x={u , v} կողի վերագրվաղ է d(x)>=0 թիվ՝ կողի երկարություն: Գտնել գոնե մեկ հատ մինիմալ կմախքային ծառ: Ովքեր չեն հիշում ծառը դա կապակցված գրաֆ է որը ցիկլ չի պարունակում: Կապակցված գրաֆի կմախքային ծառ անվանում են այն ծառը, որի գագաթների բազմությունը համնկնում է գրաֆի գագաթների բազմության հետ , իսկ կողերի բազմությունը գրաֆի կողերի բազմության ենթաբազմություն է: Այսինքն կապակցված գրաֆի կմախքային ծառը ստացվում է գրաֆի կողերի բազմությունից կողեր դեն նետելով այնպես , որ ստացված գրաֆը լինի կապակցված և ցիկլ չպարունակի:
Ով՞ կարա տա այս խնդիրը լուծող ալգորիթմ::think
Նախորդ իմ կշռաքարերի խնդիրը արժանացավ ընդամենը մեկ հոգու պատասխանի, այն էլ սխալ: Անկեղծ ասած ես սպասում էի ավելին: Ինչեվիցե միհատ էլ խնդիր, այս
անգամ գրաֆների տեսությունից: Այն անվանում են մինիմալ կմախքային ծառ գտնելու խնդիր:
Նախ ընդանուր խնդրի դրվացքը:
Ունենք n հատ քաղաք որոնք միցված են իրար
որոշակի ճանապարհներով: Ոչ մի քաղաք մեկուսացված չի մնացածից՝ այսինքն
ցանկացած երկու քաղաք միացված են ճանապարհով ,որը , միգուց է , անցնում է
մեկ այլ քաղաքով կամ քաղաքներով : Այդ ճանապարհներից ոչ մեկը ասֆալտապատաց չէ: Պահանջում է ասֆալտապատել այնպիսի մինիմալ՝ նվացագույն ծախսեր ունեցող ճանապարհ , որը անցնի բոլոր քաղաքներով:
Հիմա գրաֆների լեզվով:
Տրված է կապակցված գրաֆ:Գրաֆի յուրաքանչյուր x={u , v} կողի վերագրվաղ է d(x)>=0 թիվ՝ կողի երկարություն: Գտնել գոնե մեկ հատ մինիմալ կմախքային ծառ: Ովքեր չեն հիշում ծառը դա կապակցված գրաֆ է որը ցիկլ չի պարունակում: Կապակցված գրաֆի կմախքային ծառ անվանում են այն ծառը, որի գագաթների բազմությունը համնկնում է գրաֆի գագաթների բազմության հետ , իսկ կողերի բազմությունը գրաֆի կողերի բազմության ենթաբազմություն է: Այսինքն կապակցված գրաֆի կմախքային ծառը ստացվում է գրաֆի կողերի բազմությունից կողեր դեն նետելով այնպես , որ ստացված գրաֆը լինի կապակցված և ցիկլ չպարունակի:
Ով՞ կարա տա այս խնդիրը լուծող ալգորիթմ::think
Հի Հի Հի
կարող եմ 2 ալգորիթմ նշել Կրասկալի ու Պրիմի ալգորիտմները բայց հավես չկա նկարագրելու
teleport
01.03.2007, 03:08
Linusi առաջարկած ալգորիտմները երկուսն ել ծանոտ են.
այնպես որ մատ.
Հի Հի Հի
կարող եմ 2 ալգորիթմ նշել Կրասկալի ու Պրիմի ալգորիտմները բայց հավես չկա նկարագրելու
Այս խնդրի լոծումը նույն պես:
Այս խնդրի լոծումը նույն պես:
Ճիշտն ասած չհասկացա գրածդ
Ճիշտն ասած չհասկացա գրածդ
մատ :D
teleport
02.03.2007, 13:50
Ընդհանրապես չեմ հասկանում ինչումն է բանը:think
մատ :D
Այ մարդ մի երկու բառ ավել գրեք հասկանանք ինչ եք գրում:angry
Առաջարկված է խնդիր, պատասխանվցված է ւնդիրը լուծող 2 ալգորիթմ(անունները, Եթե ուզում եք ծանոթանալ ալգորիթմներին կարող եմ նշել գրականություն)
Ճիշտն ասած չհասկացա գրածդ
Երևի "Կշռաքարերի խնդիրը"-ում մեչբերումս չես կարդացել:
Ընդամենը ուզում էի ասեի որ խնդրի լուծումը(ալգորիթմը) արթեն գիտեմ:
Երևի "Կշռաքարերի խնդիրը"-ում մեչբերումս չես կարդացել:
Ընդամենը ուզում էի ասեի որ խնդրի լուծումը(ալգորիթմը) արթեն գիտեմ:
Հա օկ :)
մի ամիս առաջ տեղում չեի ;)
Հա օկ :)
մի ամիս առաջ տեղում չեի ;)
Բայց տարացքում էիր::acute
Ավելացվել է 19 րոպե անց
Այ մարդ մի երկու բառ ավել գրեք հասկանանք ինչ եք գրում:angry
Առաջարկված է խնդիր, պատասխանվցված է ւնդիրը լուծող 2 ալգորիթմ(անունները, Եթե ուզում եք ծանոթանալ ալգորիթմներին կարող եմ նշել գրականություն)
Ինչ՞ գրականություն կարաս նշես: Էլեկտրոնային տարբերակ կա՞:
Հավեսով խնդիր:
1-ից 40 կիլոգրամանոց բեռը կշռեք նժարավոր կշեռքի վրա` օգտագործելով 4 հատ կշռաքար;
Հավեսով խնդիր:
1-ից 40 կիլոգրամանոց բեռը կշռեք նժարավոր կշեռքի վրա` օգտագործելով 4 հատ կշռաքար;
Լավ խնդիր էր, հազիվ:) վաղուց չի եղել:
Պատասխան, 1 3 9 27,
Ակնհայտ էր:D Ծրագրավորումը մարդուն պչացնում ա, դրած անկապ կոմպ եմ մաշում, ու հլը քիչ ա չեմ մտախում, այլ ծրագիր եմ մի ամգամից գրու, ծրագիրնել առանց մտածելու պօլնիյ պերեբոր եմ անում: Ահավոր ա, ամոթ ա:
import java.util.ArrayList;
import java.util.List;
public class Qarasun {
public static void main(String[] args) {
for (int a = 0; a < 40; a++) {
for (int b = 0; b < 40; b++) {
for (int c = 0; c < 40; c++) {
for (int d = 0; d < 40; d++) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 81; i++) {
int count = 0;
int ankap = i;
if (ankap % 3 == 0) {
count += a;
}
else if (ankap % 3 == 1) {
count -= a;
}
ankap = ankap / 3;
if (ankap % 3 == 0) {
count += b;
}
else if (ankap % 3 == 1) {
count -= b;
}
ankap = ankap / 3;
if (ankap % 3 == 0) {
count += c;
}
else if (ankap % 3 == 1) {
count -= c;
}
ankap = ankap / 3;
if (ankap % 3 == 0) {
count += d;
}
else if (ankap % 3 == 1) {
count -= d;
}
list.add(count);
}
boolean bool = true;
for (int i = 0; i < 41; i++) {
if (!list.contains(i)) {
bool = false;
}
}
if (bool) {
System.out.println(a + " " + b + " " + c + " " + d);
}
}
}
}
}
}
}
Լավ խնդիր էր, հազիվ:) վաղուց չի եղել:
Պատասխան, 1 3 9 27,
Ակնհայտ էր:D Ծրագրավորումը մարդուն պչացնում ա, դրած անկապ կոմպ եմ մաշում, ու հլը քիչ ա չեմ մտախում, այլ ծրագիր եմ մի ամգամից գրու, ծրագիրնել առանց մտածելու պօլնիյ պերեբոր եմ անում: Ահավոր ա, ամոթ ա:
import java.util.ArrayList;
import java.util.List;
public class Qarasun {
public static void main(String[] args) {
for (int a = 0; a < 40; a++) {
for (int b = 0; b < 40; b++) {
for (int c = 0; c < 40; c++) {
for (int d = 0; d < 40; d++) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 81; i++) {
int count = 0;
int ankap = i;
if (ankap % 3 == 0) {
count += a;
}
else if (ankap % 3 == 1) {
count -= a;
}
ankap = ankap / 3;
if (ankap % 3 == 0) {
count += b;
}
else if (ankap % 3 == 1) {
count -= b;
}
ankap = ankap / 3;
if (ankap % 3 == 0) {
count += c;
}
else if (ankap % 3 == 1) {
count -= c;
}
ankap = ankap / 3;
if (ankap % 3 == 0) {
count += d;
}
else if (ankap % 3 == 1) {
count -= d;
}
list.add(count);
}
boolean bool = true;
for (int i = 0; i < 41; i++) {
if (!list.contains(i)) {
bool = false;
}
}
if (bool) {
System.out.println(a + " " + b + " " + c + " " + d);
}
}
}
}
}
}
}
Փաստորեն պետքա դեմից ընդհանուր դեպքը ասեի կամ գոնե կշռաքարերի քանակը չասեի..
Ուրվական
29.01.2008, 23:55
Այսուհետև կշռումների հետ կապված տրամաբանական խնդիրները կգրենք այս թեմայում:
Այգեպանն ընդամենը 3 կշռաքարով պետք է կշռի և խնձորի բերքը բաժանի 13 տոպրակի միջև՝ 1կգ, 2կգ, ..., 13 կգ խնձորներով, ընդ որում՝ դրանցից յուրաքանչյուրը նա ցանկանում է ստանալ՝ միայն մեկ կշռում կատարելով: Ինչպիսի՞ զանգվածներով կշռաքարեր պետք է ընտրի այգեպանը:
:)
Կարելի է մի հատ դժվար խնդիր տամ? :P
Ուրեմն ունենք 12 մետաղադրամ, որոնցից մեկը կեղծ է և կամ ավելի ծանր է մյուսներից, կամ ավելի թեթև: Ունենք նաև նժարավոր կշեռք: Ընդամենը 3 անգամ կշռելով գտեք կեղծ մետաղադրամը:
Safaryan
12.03.2008, 16:36
Կարելի է մի հատ դժվար խնդիր տամ? :P
Ուրեմն ունենք 12 մետաղադրամ, որոնցից մեկը կեղծ է և կամ ավելի ծանր է մյուսներից, կամ ավելի թեթև: Ունենք նաև նժարավոր կշեռք: Ընդամենը 3 անգամ կշռելով գտեք կեղծ մետաղադրամը:
Բաժանում ենք 2 մասի՝ 6ական: կշռելով մեկը ծանր կլինի: Էդ ծանր մասը բաժանում ենք էլի 2 մասի՝ 3ական: Կշռում ենք, Էլի ընտրում ենք ծանր մասը: Հետո էդ երեքից ցանկացած երկուսը ընտրում ենք: Կշռում: Որը ծանր եղավ, ուրեմն կեղծը հենց դա է, եթե իրար հավասար են լինում , ուրեմն կեղծը էն տակի մնացողն է::)
Բաժանում ենք 2 մասի՝ 6ական: կշռելով մեկը ծանր կլինի: Էդ ծանր մասը բաժանում ենք էլի 2 մասի՝ 3ական: Կշռում ենք, Էլի ընտրում ենք ծանր մասը: Հետո էդ երեքից ցանկացած երկուսը ընտրում ենք: Կշռում: Որը ծանր եղավ, ուրեմն կեղծը հենց դա է, եթե իրար հավասար են լինում , ուրեմն կեղծը էն տակի մնացողն է::)
Դե էլ չասեմ, որ պատասխանդ լիարժեք չէ... :P
Իսկ եթե կեղծ մանրադրամը ավելի թեթև է? :)
Safaryan
12.03.2008, 16:42
Դե էլ չասեմ, որ պատասխանդ լիարժեք չէ... :P
Իսկ եթե կեղծ մանրադրամը ավելի թեթև է? :)
Վաղը մարդավարի կգրեմ, եթե մինչև էդ գրող չլինի, բայց հիմա ահավոր շտապում եմ::B
Կարելի է մի հատ դժվար խնդիր տամ? :P
Ուրեմն ունենք 12 մետաղադրամ, որոնցից մեկը կեղծ է և կամ ավելի ծանր է մյուսներից, կամ ավելի թեթև: Ունենք նաև նժարավոր կշեռք: Ընդամենը 3 անգամ կշռելով գտեք կեղծ մետաղադրամը:
Կներեք որ ուշացրեցի պատասխանս , տանից ակումբ ոչ մի կերպ չէի կարողանում կպնել :( Դե հիմա պատասխանս
Նախ ես այդ 12 կշռաքարերը կբաժանեմ 3 խմբի , որոնցից յուրաքանչյուրում կլինի 4 պատահական կշռաքար ։
Սկզբում կկշռեմ 2 քառյակներ։
1. Առաջին քառյակի ընդհանուր կշիռը հավասար է 2-րդ քառյակի ընդհանուր կշռին ։
Պարզ է որ տարբերություն կշռաքարը 3-րդ քառյակում է ։
Առաջին քառյակից պատահական 3 կշռաքար կկշռեմ 3-րդ /տարբերություն պարունակող / քառյակի պատահական 3-ի հետ ։ Եթե այս դեպքում էլ ստացվեց նույնը ապա վեջին կշռաքարը 4-րդ խմբից կկշռեմ ցանկացած կշռաքարի հետ և կպարզեմ այն ծանր է թո թեթր , քանի որ այդ կշռաքարը հենց տարբերություն կշռաքարն էր ։
1. Սկզբում կշռել էի առաջին և 2-րդ քառյակներն ու հավասար էին ։ Կշռում եմ առաջինի և 4-րդի եռյակներն ու ստացվում է , որ նրանք տարբեր են ։ Այս դեպքում ակնհայտ է , որ 4-րդ խմբակի այս վերցրակ եռյակից մեկը տարբերություն կշռաքառն է ։ Քանի որ ասացինք ու առաջինի եռյակի և 4-րդի եռյակի կշռումը տարբերություն էր ցույց տվել , հետևաբար մենք արդեն գիտեքն այն ծանր է թե թեթև ։ այս դեպում կվերցնենք 4-րդ քառյակի վերը նշված եռյակն ու նրանից ցանկացած 2-ը կկշռենք իրար հետ ։ Եթե տարբերույեւն հանդիպենք ապա գտանք տարրը , եթե հավասար լինեն ապա եռյակի մնացյալ տարրն էր տարբերություն տարրը ։
3. Կշռում ենք առաձին քառյակը 2-րդ քառյակի հետ սակայն ունենք տարբերություն ։
Ենթադրենք առաջին քառյակը ծանր էր 2-րդ քառյակից ։ Այժմ առաջին քառյակի տարրերին պայմանականորեն անվանենք ծանր , երկրորդ քառյակի տարրերին պայմանականորեն անվանենք թեթեև իսկ 3-րդ չկծռված քառյակին անվանենք նորմալ ։
Վերցնում ենք 1նորմալ 1ծանր 1թեթև կշռաքար ու կշռում 2ծանր 1թեթև կշռաքարերի հետ ։
Եթե 1նորմալ 1ծանր 1թեթև > 2ծանր 1թեթև , ապա կամ ձախ մասում ունենք 1ծանր կշռաքար , կամ աջում 1 թեթեև կծռաքար ։ սրանցից մեկն ու մեկը , օրինակ 1ծանրը ձախ մասին կկշռենք նորմալի հետ եթե ծանր լինի ուրեմն գտանք ծանր կշռաքար , եթե հավասար /քանի որ թեթև չի կարող լինել / ապա մեր աջմասի թեթեև կշռաքարն էր ։
Եթե 1նորմալ 1ծանր 1թեթև < 2ծանր 1թեթև , ապա կամ ձախ մասում ունենք մեկ թեթև կամ աջ մասում 2 խանրերից մեկը ծանր է ։այս դեպքում կվերցնենք 1թեթև 1ծանր և կկշռենք 2նորմալի հետ , եթե թեթև ստացվի ուրեմն թեթևն էր , եթե ծանր ուրեմն ծանրն էր մ եթե հավասար , ապա այս աջ մասի մյուս ծանր էր ։
Եթե 1նորմալ 1ծանր 1թեթև = 2ծանր 1թեթև , ապա կամ չվերցրած 2թեթրներից մեկը թեթեև էր , կամ չվերցրած ծանրերից մեկը ծանր ։
նույն սկզբունքով վերցնում ենք 1թեթև 2խանր կշռում 2 նորմալի հետ
Եթե ծանր է ուրեմն վերցրած ծանր էր , եթե թեթև ուրեմն վերցրած թեթևմն էր , եթե հավասար ուրեմն մնացյալ 4-րդ թեթևն էր ։ :hands
Դայանա-ն :B :lol
Սա արդեն եղել է ;)
Սա արդեն եղել է ;)
Ափսոս, չգիտեի :)
Ափսոս, չգիտեի :)
;) եթե էլի տրամաբանական խնդիրներ ունս գրի լա՞վ, փորձենք մտածել ;)
petros59
13.11.2009, 07:09
;) եթե էլի տրամաբանական խնդիրներ ունս գրի լա՞վ, փորձենք մտածել ;)
Ունենք նժարավոր կշերք, կշռաքարեր և 10 պարկ մետաղյա դրամներ :Պարկերից մեկում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել թե ո՞ր պարկում են կեղծ դրամները:
Այս խնդիրը հին խնդիր է:Այն լուծելուց հետո փորձեք.
Ունենք նժարավոր կշերք, կշռաքարեր և 5 պարկ մետաղյա դրամներ :Պարկերից երկուսում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել թե ո՞ր պարկերում են կեղծ դրամները:
Վերջապես. Ունենք նժարավոր կշերք, կշռաքարեր և N պարկ մետաղյա դրամներ :Պարկերից m-ում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել ո՞ր պարկերում են կեղծ դրամները:
petros59
13.11.2009, 07:12
Այսուհետև կշռումների հետ կապված տրամաբանական խնդիրները կգրենք այս թեմայում:
Այգեպանն ընդամենը 3 կշռաքարով պետք է կշռի և խնձորի բերքը բաժանի 13 տոպրակի միջև՝ 1կգ, 2կգ, ..., 13 կգ խնձորներով, ընդ որում՝ դրանցից յուրաքանչյուրը նա ցանկանում է ստանալ՝ միայն մեկ կշռում կատարելով: Ինչպիսի՞ զանգվածներով կշռաքարեր պետք է ընտրի այգեպանը:
:)
1; 2; 4
petros59
27.01.2010, 21:23
Ունենք նժարավոր կշերք, կշռաքարեր և 10 պարկ մետաղյա դրամներ :Պարկերից մեկում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել թե ո՞ր պարկում են կեղծ դրամները:
Այս խնդիրը հին խնդիր է:Այն լուծելուց հետո փորձեք.
Ունենք նժարավոր կշերք, կշռաքարեր և 5 պարկ մետաղյա դրամներ :Պարկերից երկուսում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել թե ո՞ր պարկերում են կեղծ դրամները:
Վերջապես. Ունենք նժարավոր կշերք, կշռաքարեր և N պարկ մետաղյա դրամներ :Պարկերից m-ում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել ո՞ր պարկերում են կեղծ դրամները:
Այս խնդրին ոչ ոք չարձագանքեց,այն դեպքում որ դրանցից առաջինը դժվար չէ: Չգիտեմ գրեմ լուծումները թե
Ունենք նժարավոր կշերք, կշռաքարեր և 10 պարկ մետաղյա դրամներ :Պարկերից մեկում դրամները կեղծ են: Կեղծը թեթև է իսկականից 1 գրամով: Ընդամենը 1 կշռումով որոշել թե ո՞ր պարկում են կեղծ դրամները:
Կարողա՞ սլաքավոր կշեռք լինի:
petros59
28.01.2010, 09:43
Փորցեք սլաքաորվ:Այդ դեպքում մի պայման ավելացնում եմ: Իսկական մետաղադրամի կշիռը 10 գրամ է:
Փորցեք սլաքաորվ:Այդ դեպքում մի պայման ավելացնում եմ: Իսկական մետաղադրամի կշիռը 10 գրամ է:
Այդ դեպքում հեշտ է: Առաջին պարկից դնում ես 1 մետաղյա դրամ, երկրորդից 2, և այդպես…
Ստացվում է 55 մետաղյա դրամ, որի ընդհանուր քաշը ոչ կեղծ մետաղյա դրամների դեպքում պետք է լինի 550 գրամ:
Վերջում, ինչքան պակասի 550 գրամից, ըստ այդմ էլ կորոշվի կեղծ մետաղյա դրամներով պարկը:
1 գրամ պակասելու դեպքում առաջին պարկ և այդպես…
petros59
28.01.2010, 21:58
նւյն բանը կարող եիք անել նժառավոր կշեռքով, ողակի նժարներից մեկի վրա դնում եք որևէ պարկից 55 հատ և հավասարակշռում կշռաքարերի օգնությամբ:
Հիմա կարող եք անցնել երկրորդ խնդրի լուծմանը: Հաջողություն: