პირველი:

გვაქვს 1დან N-მდე (1<N<8) რიცხვები არეული ინფუთში. K-ური შემობრუნების ოპერაცია ვუწოდოთ ამ დალაგებულ სიმრავლეზე პირველი K რიცხვის შემობრუნებას (23415 k=3 => 43215).


უნდა გავიგოთ მინიმუმ რამდენი ოპერაცია დაგვჭირდება დასასორტირებლად.


ახლა ჩემი ამოხსნა სწორია თუ არა მაინტერესებს.

ჩემი ამოხსნა:


1 ჯერ ვიგებთ თუ არის დასორტირებული უკვე თუ კი გასაგებია თუ არა ვაგრძელებთ
2 ერთიანს გადავიტანთ ბოლოში შემდეგნაირად: სადაც არის ახლა იმ ინდექსით გავაკეთებთ შემობრუნების ოპერაციას, მერე მთლიანი შემობრუნებას ვაკეთებთ.

3 შემდეგ ვატარებთ (2) ოპერაციებს ოღონდ უკვე არა ერთისთვის არამედ ორისთვის (ანუ რეკურსია გაკეთდება ერთით ნაკლები სიმრავლისთვის)

4 საბოლოოდ K=N -ურად შემოვაბრუნებთ.


ასეა? თუ კი მაშინ რვა რატომ იყო ნის ზედა საზღვარი?




ამოცანის გარკვეულობისთვის მაგალითიც იყოს:


4231-ზე პასუხია 4 რადგან:

4231->3241->2341->4321----->1234;

ასეთი ტესტი განიხილე:
23145

შენი ალგორითმით, როგორც მივხვდი, ასე დაალაგებ:

23145 -> 13245 -> 54231 -> 24531 -> 35421 -> 45321 -> 54321 -> 12345

ოპტიმალურად კი ასე დალაგდება:

23145 -> 32145 -> 12345

@ვარლევანი, მადლობა.

მდა, მართალია.

ჰმ, მაშინ ვნახავ უკვე არის თუ არა უკვე დალაგებული რაღაც ბოლო ნაწილი. აი ამ შემთხვევაში შეამოწმებოდა რომ ბოლო ორს აღარ უნდა არაფერი და ფუნქციას გაუშვებდა პირველ სამზე. და მანდ უკვე სწორად გამოდის.

ერთიანს დატოვებდა ბოლოში დამერე ორზე გაუშვებდა ეტც.


კიდევ არის რამე?:/

Dixtosa
შეგიძლია დაამტკიცო შენი ალგორითმის სისწორე?

იმედია, უბრალოდ ვარაუდი არაა რასაც წერ :)

varlevani,
ვერა. ინდუქციით? მთლინად ინტუიციაზეა :ნოდ: ხდ. არაა სწორი?


თან ამოცანის პირობაში ეწერა კიდევ რომ 2*ნ-2 დრო არის მაქსიმუმიო (და ნუ ბაღნებს მიანიშნესავით ალბათ რომ მინიმუმიც ეგ იქნებოდა).