[C#] Домашно Multidimensional Arrays - 4 задача


1

Условие: Write a program, that reads from the console an array of N integers and an integer K, sorts the array and using the method Array.BinSearch() finds the largest number in the array which is ≤ K. Решениеsource.

Обяснение: Първо сортираме масива с Quick Sort от миналото домашно, след това извършваме двоично търсене, като взимаме граничните случаи предвид. Накрая отпечатваме индекса на елемента и неговата стойност.



Отговори



8

 

В условието е казано, че трябва да се използва задължително Array.BinarySearch(). Задачата е дадена с друга цел - да си прочетеш документацията, а именно:

"If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value. If value is not found and value is greater than any of the elements in array, a negative number which is the bitwise complement of (the index of the last element plus 1)." 

Решението ти работи, но не е съобразено с условието на задачата.

http://pastebin.com/Mrg0Chny


от ilovehomework (200 точки)


0
Всичко чудесно, но не става ли дума за многомерен масив. През цялото време ти работиш с едномерен. Няма лошо мисля , че принципа горе-долу е същия, но не се отнася за поставената задача.


0
Array.BinarySearch

от ivan.pudev (140 точки)



1
Метода в .NET Framework е BinarySearch(); . Ако в условието пише BinSearch();, аз го разбирам, че трябва сами да направим разширяващ метод. :)

от kirov (4821 точки)


0
Ъъм... не. Ако беше така, щеше да е упоменато изрично в условието това, а и нямаше да се говори с такава конкретика. Ако трябва сам да си напишеш метод, няма да пише в условието "Use the method X", а преди това ще е казано конкретно да се създаде метод X. Подразбира се, че това се отнася за някой готов метод. Това, че в условието пише BinSearch() e най-вероятно просто грешка. Furthermore, ако прегледаш презентацията за School Academy (която е същата, с малки tweaks), ще видиш, че там има същата задача, но там името на функцията е изписано коректно.

от ilovehomework (200 точки)

0
Просто споделям наблюдение :) Не съм гледал лекцията на School Academy. Така ми се стори логично.

от kirov (4821 точки)


8

 

Според мен в задачата се използва - Array.BinarySearch(array, k)
 
Метода работи по следния начин:
1) връща стойност индекса на елемента "к" в масив "array"
2) ако върнатото число < 0 - не е намерин елемент к
3) aкo върнатото число >= 0 - връща индекса на елемента
 
Това е моето решение с този метод.
http://pastebin.com/UKHGjm6p
Най-отдоло в кода съм разписал примерен тест.

от ivivanov (903 точки)


0
Да, но в условието пише и че трябва да намерим елемента с най-голяма стойност, който е по-малък или равен на "K", т.е. когато не намираме "К" трябва да проверим на коя позиция би бил в масива и да покажем предишния елемент.

от gallumbits (2371 точки)

0
Дам точно така. Така съм го и написал да работи...

от ivivanov (903 точки)



3

Аз открих, че ако върнатото число е < 0, тогава ето така намираме най-голямото число, което е по-малко или равно на K:

array[-index-2]

където index e върнатото число..

Пробвах го 5-6-7 пъти и показваше вярно, някой ако открие грешка да казва:

http://pastebin.com/mPyFuc9u


от kalin4o (487 точки)


0
няма как да имаш грешка ;) Това е идеята на върнатата отрицателна стойност, като ~index ти връща първия елемент, по-голям от търсения, следователно ~index - 1 ще ти даде най-големия, който е по-малък от търсения.

от kdikov (3407 точки)

0
Не си взел предвид случая, когато Array.BinarySearch връща -1, т.е. когато първият елемент в масива е по-голям от К. Примерен вход: int[] arrayElements = {4,5}; K = 3;

от gallumbits (2371 точки)



14

Задача 4 ( и 5) с разяснение на Array.BinarySearch и как се работи с отрицателните стойности, които връща.


от kdikov (3407 точки)


0
Аз пък помисих, че в задачата се изисква сами да го измислим тоя метод, щото търсих за array.binsearch и нищо не излезе. Супер,мерси много ;)

от AlexPopov (1568 точки)


1
Това е единствената задача, която ми се стори по лесна от останалите.Направих я с един while(true) и вътре си намалявам К и break като индекса е <= K
http://pastebin.com/YZW61HTR

от iwitass (3695 точки)


2
Вкарвам К в масива преди сортирането и после е лесно, но може би не е съвсем коректно спрямо условието или поне спрямо идеята на задачата, но ако не знаеш какво значи отрицателното число върнато от BinarySearch и/или имаш възможност да увеличаваш размера на масива, е все пак вариант :)
http://pastebin.com/SbwF00T9

от shristoff (747 точки)


0

Логиката е ясна, вече е обяснена, няма да се повтарям...Благодаря на kdikov за перфектно обяснената информация в блога му...перфектен!

 

BinarySearch


от zhelyazkovn (2949 точки)


0
Това е моето решение - http://pastebin.com/zBVJbzKe
Първо сортирам масива с Array.Sort(). След това използвам един while цикъл в който се пуска BinarySearch() върху масива. Ако върната стойност е -1 или по абсолютна стойност е > от броя на елементите на масива, това означава, че числото К е извън масива и излизам от цикъла и програмата печати съобщение - няма намерен елемент. В противен случай намалявам К с единица (К--), и отново се изпълнява BinarySearch() върху масива. Това се прави докато върната стойност , т.е. индекс на елемента и самият елемент е равен на текущата стойност на К. Накрая програмата печати "largest number".

от szaekov (155 точки)


0

Моето решение: http://pastebin.com/vmz5kFS1

Написала съм коментари за всеки етап на задачата, изпозвах "a[~index - 1]" за елемента по-малък от к и с един for else обхванах трите случая.


от son4etyyy (416 точки)