Grocking algorithms or a painless introduction to algorithms

ڪتاب جو جائزو "Grocking Algorithms". ٿورڙي ذاتي راء، چند مثال. مون کي اميد آهي ته هي جائزو توهان کي سمجهڻ ۾ مدد ڏيندو ته ڇا توهان هن ڪتاب کي پڙهڻ چاهيو ٿا يا ڇا اهو توهان جي شيلف تي ان جي جاءِ نه وٺندو. خبردار: گھڻا متن)

"گروڪنگ الگورٿمز" يا الورورٿمز جو بي درد تعارف

تعارف

تقريبن ڪنهن به جونيئر سطح جي خالي جاين تي گهرجون آهن جهڙوڪ "ڊيٽا جي جوڙجڪ ۽ الگورتھم جي ڄاڻ." انهن لاءِ جن وٽ خاص تعليم آهي، الورورٿم عام ڪورس ۾ شامل آهن ۽ ڪو مسئلو نه هجڻ گهرجي. پر ڇا جيڪڏهن ترقي ٻين قدمن مان آندو ويو؟ باقي اهو سڀ ڪجهه پنهنجي پاڻ تي سکڻ آهي. ان سوال جو جواب آهي ته ”ڪنهن جو الزام آهي“، پر ”ڇا ڪجي“ جي سوال جو جواب ضرور ڳولڻو آهي. اچو ته ڪتابن ۾ ڏسو. ۽ مان توھان کي ھڪڙي بابت ٻڌائڻ چاھيان ٿو.

گروڪ الگورتھم

سڀني ڪمن جي وچ ۾، مون کي "گروڪنگ الگورتھم" وانگر هڪ ڪتاب مليو. توھان وڌيڪ ڳولي سگھوٿا ھتي: " ڪتاب "وڌندڙ الگورتھم. پروگرامرز ۽ شوقينن لاءِ ھڪڙو نمايان ھدايتون ." مون ڪتاب گهڻو وقت اڳ ڏٺو، پر اوزون تي ان جي قيمت 680 روبل آهي. قيمتي يا سستو - هرڪو پاڻ لاء فيصلو ڪري ٿو. مان پهريان ئي Avito تي ٻيو ڪتاب اڌ قيمت تي خريد ڪري رهيو آهيان. سو مون ان کي سينٽ پيٽرسبرگ ۾ مليو، خريد ڪيو، ۽ گهمڻ ڦرڻ لاءِ ويس. جيڪو مون توهان سان شيئر ڪرڻ جو فيصلو ڪيو آهي. ها، ڪتاب ۾ ڪو به جاوا ڪوڊ ناهي، پر اتي آهي... ٻيو ڪوڊ، پر پوءِ ان تي وڌيڪ.

Algorithms جو تعارف (منتخب ترتيب)

تنهن ڪري، بيان جي هڪ آسان شڪل ۾، اسان پنهنجي ڪارڪردگي ۾ پهرين ترتيب تي پهچون ٿا. هي آهي چونڊ ترتيب. ان جو خلاصو اهو آهي ته اسان عنصرن جي ذريعي وڃون ٿا کاٻي کان ساڄي (0 عنصر کان آخري تائين)، ۽ باقي عناصر مان سڀ کان وڏو ڳوليو. جيڪڏهن اسان ان کي ڳوليندا آهيون، پوء اسان ان عنصر کي تبديل ڪريون ٿا جنهن تي اسان هاڻي آهيون ۽ سڀ کان وڏو عنصر. هڪ صف جي باري ۾ پهريون سوچڻ جو آسان طريقو آهي: [5, 3, 6, 2, 10]. ڪاغذ جو هڪ ٽڪرو وٺو، هڪ قلم (سڀ کان آسان ۽ سڀ کان وڌيڪ قيمتي طريقو) ۽ تصور ڪريو ته اسان وٽ ڪيئن آهي هڪ کاٻي سرحد، هڪ موجوده انڊيڪس (يا ساڄي سرحد)، ۽ گهٽ ۾ گهٽ عنصر جو هڪ انڊيڪس. ۽ اسان ان سان ڪيئن ڪم ڪريون ٿا. مثال طور: Algorithms اڪثر pseudocode ۾ بيان ڪيا ويا آهن، مثال طور، وڪيپيڊيا تي. اسان جو بلڪل pseudocode نه آهي، پر ان تي وڌيڪ بعد ۾. ھاڻي اچو ته ڏسون:

def selectionSort(array):
    for left in range(0, len(array)):
        minIndex = left
        for right in range (left+1, len(array)):
            if array[right] < array[minIndex]:
                minIndex = right
        if minIndex != left:
            temp = array[left]
            array[left] = array[minIndex]
            array[minIndex] = temp
    return array

print(selectionSort([5, 3, 6, 2, 10]))

هاڻي اچو ته ان کي جاوا ڪوڊ جي صورت ۾ پيش ڪريون:

public static void selectionSort(int[] array) {
        for (int left = 0; left < array.length; left++) {
            int minIndex = left;
            for (int right = left+1; right < array.length; right++) {
                if (array[right] < array[minIndex]) {
                    minIndex = right;
                }
            }
            if (minIndex != left) {
                int temp = array[left];
                array[left] = array[minIndex];
                array[minIndex] = temp;
            }
        }
}

جئين توهان ڏسي سگهو ٿا، ڪوڊ لڳ ڀڳ ساڳيو آهي. پهريون ڪوڊ ڪتاب مان هڪ مثال آهي. ٻيو آهي منهنجي مفت عملدرآمد جاوا ڪوڊ ۾.

ورجائي

اڳتي هلي اسان کي ٻڌايو وڃي ٿو ته اتي هڪ اهڙي شيءِ آهي جيڪا ٻيهر ورجائي ٿي. سڀ کان پهريان، هڪ هاريءَ بابت مسئلو آهي جنهن وٽ AxB سائيز جي فيلڊ آهي. اهو ضروري آهي ته هن فيلڊ کي برابر "چورس" ۾ ورهايو وڃي. ۽ پوءِ ان کان پوءِ Euclid Algorithm جو ذڪر ڪيو ويو آهي. جيڪو مون کي پسند ناهي اهو آهي ته انهن ان جو ڪوڊ لکڻ جي ڪوشش نه ڪئي. پر Euclid الگورتھم سادو ۽ اثرائتو آھي: ايماندار ٿيڻ لاءِ ، مون ڪتاب ۾ ڪجهه تفصيل ياد ڪيا ، جهڙوڪ هن وڊيو ۾: “ معلومات. الگورتھم جو نظريو. Euclid جي الگورتھم . " مثال طور، جيڪڏهن a b کان گهٽ آهي، ته پوءِ پھرين رن دوران b ۽ a جڳهيون تبديل ڪندا ۽ ٻئي ڀيري وڏي کي ننڍي ۾ ورهايو ويندو. تنهن ڪري، دليلن جو حڪم اهم نه آهي. عام طور تي، پهرين اسين ڪاغذ جي هڪ ٽڪري تي الگورتھم کي "محسوس" ڪري سگھون ٿا: هاڻي اچو ته ڪوڊ ڏسو:

def euclidean(a, b):
    if a == 0 : return b
    if b == 0 : return a
    return euclidean (b, a % b)

اچو ته ساڳيو ڪوڊ جاوا ۾ لکون. جيڪڏهن گهربل هجي، اسان آن لائن ڪمپلر استعمال ڪري سگهون ٿا :

public static int euclid(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        return euclid(b, a%b);
}

ڪتاب جي شروعات ۾ فڪري به ذڪر ڪيو ويو آهي. هڪ عدد n (n!) جو فيڪٽري 1 کان n تائين انگن جي پيداوار آهي. ائين ڇو ڪيو؟ هتي هڪ عملي درخواست آهي. جيڪڏهن اسان وٽ n شيون آهن (مثال طور، n شهر)، پوء اسان انهن مان ٺاهي سگهون ٿا! مجموعا. توھان پڙھڻ بابت وڌيڪ پڙھي سگھو ٿا ھتي: " Recursion. ٽريننگ جا ڪم ." ورهاڱي ۽ ورهاڱي واري طريقن جو مقابلو: " ٻيهر "

جلدي ترتيب

تڪڙو ترتيب هڪ بلڪه دلچسپ الگورتھم آهي. ڪتاب هن ڏانهن گهڻو ڌيان نه ٿو ڏئي. ان کان علاوه، ڪوڊ صرف بدترين صورت ۾ ڏنو ويو آهي، جڏهن پهريون عنصر چونڊيو ويو آهي. بهرحال، شايد پهرين واقفيت لاء، هي مثال ياد ڪرڻ آسان ٿي ويندو. ۽ اهو بهتر آهي ته هڪ خراب جلدي لکڻ کان وڌيڪ نه لکجي. هتي ڪتاب مان هڪ مثال آهي:

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

هتي هر شي سپر سادو آهي. جيڪڏهن اسان وٽ 0 يا 1 عنصر جو هڪ صف آهي، ان کي ترتيب ڏيڻ جي ڪا ضرورت ناهي. جيڪڏهن اهو وڏو آهي، اسان صف جو پهريون عنصر وٺون ٿا ۽ ان کي "محور عنصر" سمجهيو. اسان 2 نيون صفون ٺاھيون ٿا - ھڪڙي عنصرن تي مشتمل آھي پيوٽ کان وڏو، ۽ ٻئي ۾ عناصر ننڍا آھن. ۽ اسان ٻيهر ورجائيندا آهيون. بهترين اختيار نه، پر ٻيهر، بهتر ياد. اچو ته هن الگورتھم کي جاوا ۾ لاڳو ڪريو، پر وڌيڪ صحيح طور تي. نظرثاني مان مواد " جاوا اسڪرپٽ ۾ ڪمپيوٽر سائنس: Quicksort " اسان جي مدد ڪندو . ۽ ڪوڊ لکڻ کان اڳ، اچو ته ٻيهر ٺاھيون ”محسوس“ ڪرڻ لاءِ الگورٿم: پھريون، اچو ته وري ڪاغذ جي ھڪڙي ٽڪري تي ٺاھيون ته جيئن الگورٿم کي سمجھڻ لاءِ. اهو مون کي لڳي ٿو ته سڀ کان وڌيڪ خطرناڪ لمحن مان هڪ آهي مڪمل طور تي مسئلن کي حل ڪرڻ. تنهن ڪري، اسان ڪيترن ئي ننڍن قدمن ۾ عمل درآمد ڪنداسين:

• اسان کي هڪ صف ۾ عناصر کي تبديل ڪرڻ جي قابل ٿيڻو پوندو:

  private static void swap(int[] array, int firstIndex, int secondIndex) {
          int temp = array[firstIndex];
          array[firstIndex] = array[secondIndex];
          array[secondIndex] = temp;
  }




• اسان کي ھڪڙي طريقي جي ضرورت آھي جيڪا مخصوص وقف ۾ صف کي 3 حصن ۾ ورهائي

  
  

  private static int partition(int[] array, int left, int right) {
          int pivot = array[(right + left) / 2];
          while (left <= right) {
              while (array[left] < pivot) {
                  left++;
              }
              while (array[right] > pivot) {
                  right--;
              }
              if (left <= right) {
                  swap(array, left, right);
                  left++;
                  right--;
              }
          }
          return left;
  }

  تفصيل مٿي ڏنل لنڪ تي. مختصر ۾، اسان کاٻي ڪرسر کي منتقل ڪندا آهيون جيستائين عنصر pivot کان گهٽ نه آهي. ساڳئي طرح، ساڄي ڪرسر کي ٻئي پڇاڙيء کان منتقل ڪريو. ۽ اسان ادل بدل ڪندا آهيون جيڪڏهن ڪسر نه ملندا آهن. اسان جاري رکون ٿا جيستائين ڪسرون گڏ نه ٿين. اسان هڪ انڊيڪس واپس ڪريون ٿا جيڪو وڌيڪ پروسيسنگ کي 2 حصن ۾ ورهائي ٿو.

• اتي هڪ جداگي آهي، اسان کي پاڻ کي ترتيب ڏيڻ جي ضرورت آهي:

  public static void quickSort(int[] array, int left, int right) {
          int index = 0;
          if (array.length > 1) {
              index = partition(array, left, right);
              if (left < index - 1) {
                  quickSort(array, left, index - 1);
              }
              if (index < right) {
                  quickSort(array, index, right);
              }
          }
  }

  اھو آھي، جيڪڏھن صف ۾ گھٽ ۾ گھٽ ٻن عناصر شامل آھن، پوء اھي اڳ ۾ ئي ترتيب ڏئي سگھجن ٿيون. سڀ کان پهريان، اسان سڄي صف کي ٻن حصن ۾ ورهايو، عناصر پيوٽ کان ننڍا ۽ عناصر وڏا. ان کان پوء اسان نتيجو حصن مان هر هڪ لاء ساڳيو ڪم ڪندا آهيون.

  ۽ امتحان لاء:

  public static void main(String []args){
          int[] array = {8,9,3,7,6,7,1};
          quickSort(array, 0, array.length-1);
          System.out.println(Arrays.toString(array));
  }

ڪتاب ۾ چيو ويو آهي ته هي الگورتھم نام نهاد ”تقسيم ۽ فتح“ الگورتھم سان تعلق رکي ٿو، جڏهن پروسيس ٿيل ڊيٽا سيٽ کي هر وقت اڌ ۾ ورهايو ويندو آهي. الگورتھم پيچيدگي: O(nLogn) ڇا خراب آهي (يعني، جيڪو مون کي پسند نه ڪيو) اهو آهي ته ڪتاب ۾ ضم ٿيڻ جي ترتيب جو ذڪر آهي، پر ڪو به مثال يا ڪوڊ مهيا نٿو ڪري. وڌيڪ تفصيل هتي ڳولهي سگهجن ٿا: " معلومات. ڳولها ۽ ترتيب ڏيڻ الگورتھم: ضم ڪريو ترتيب ". تنهن ڪري، مستقل مزاجي جي خاطر، اچو ته اهو پاڻ ڪريون. الورورٿم پاڻ، يقينا، فطري طور تي سادو ۽ سڌو آهي:

public static void mergeSort(int[] source, int left, int right) {
    if ((right - left) > 1) {
        int middle = (right + left) / 2;
        mergeSort(source, left, middle);
        mergeSort(source, middle + 1, right);
    }
    merge(source, left, right);
}

اسان وچين جو اندازو لڳايو ۽ صف کي اڌ ۾ ورهايو. هر اڌ لاء اسين ساڳيو ڪندا آهيون ۽ ائين ئي. اسٽاپنگ حالت يا بنيادي صورت - اسان کي لازمي طور تي هڪ کان وڌيڪ عنصر هجڻ گهرجي، ڇو ته اسان هڪ عنصر کي ٻن حصن ۾ ورهائي نٿا سگهون. هاڻي اسان کي انضمام کي لاڳو ڪرڻ جي ضرورت آهي، اهو آهي، ضم:

public static void merge(int[] array, int from, int to) {
    int middle = ((from + to) / 2) + 1;
    int left = from;
    int right = middle;
    int cursor = 0;

    int[] tmp = new int[to - from + 1];
    while (left < middle || right <= to) {
        if (left >= middle) {
            tmp[cursor] = array[right];
            System.out.println("Остаток справа: " + array[right]);
            right++;
        } else if (right > to) {
            tmp[cursor] = array[left];
            System.out.println("Остаток слева: " + array[left]);
            left++;
        } else if (array[left] <= array[right]) {
            tmp[cursor] = array[left];
            System.out.println("Слева меньше: " + array[left]);
            left++;
        } else if (array[right] < array[left]) {
            tmp[cursor] = array[right];
            System.out.println("Справа меньше: " + array[right]);
            right++;
        }
        cursor++;
    }
    System.arraycopy(tmp, 0, array, from, tmp.length);
}

هتي تبصرو ڪرڻ لاء گهڻو ڪجهه ناهي. متغيرن جي نالن مان printlnسڀ ڪجهه واضح آهي. خير، چيڪ ڪرڻ لاء:

int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));

هيش ٽيبل

ڪتاب پڻ هيش ٽيبل تي هٿ رکي ٿو. توهان کي ان کي پاڻ تي لاڳو ڪرڻ جي ضرورت ناهي، ۽ هيش ٽيبل جو جوهر بلڪل سادو آهي. سڀ کان پوء، جاوا پڻ هش ٽيبل، java.util.HashTable جو عمل درآمد ڪيو آهي. جيڪڏهن اسان HashTable ڊيوائس تي نظر وجهون ٿا، اسان ڏسنداسين ته داخلا صف اندر رهندي آهي. داخلا هڪ رڪارڊ آهي جيڪو هڪ ميلاپ آهي Key - Value. HashTable ۾ ابتدائي صلاحيت آھي - اھو آھي، شروعاتي سائيز. ۽ loadFactor - لوڊ فيڪٽر. ڊفالٽ 0.75 آهي. هي نمبر توهان کي ٻڌائي ٿو ته ڪهڙي قسم جي سرن جي لوڊ (عناصر جو تعداد / ڪل تعداد) سائيز کي وڌائڻ جي ضرورت آهي. جاوا ۾ اهو 2 ڀيرا وڌائي ٿو. ڪتاب وضاحت ڪري ٿو ته Hash جدولن کي hash tabs سڏيو ويندو آهي ڇاڪاڻ ته hash function جي بنياد تي، array cell (basket) جنهن ۾ Entry. توھان پڻ وڌيڪ پڙھي سگھو ٿا ھتي: تصويرن ۾ ڊيٽا جي جوڙجڪ. HashMap ۽ LinkedHashMap . توهان ان کي ڪتابن ۾ پڻ پڙهي سگهو ٿا. مثال طور هتي: " HashTable بنياديات "

گرافس، بيڊٿ فرسٽ سرچ (ننڍڙي واٽ جي ڳولا)

شايد سڀ کان وڌيڪ دلچسپ موضوعن مان هڪ گرافس آهي. ۽ هتي، صحيح هجڻ لاء، ڪتاب انهن ڏانهن تمام گهڻو ڌيان ڏئي ٿو. شايد ان ڪري هي ڪتاب پڙهڻ لائق آهي. جيتوڻيڪ، شايد، اهو ٿورو وڌيڪ واضح طور تي بيان ڪري سگهجي ٿو)) پر، اسان وٽ انٽرنيٽ آهي ۽ ڪتاب کان علاوه، توهان هن پلے لسٽ کي نظريي تي ڏسي سگهو ٿا "جيڪي پهريون ڀيرو گراف بابت ٻڌي رهيا آهن . ” خير، قدرتي طور، ڪتاب جي بلڪل شروعات ۾، بيڊٿ فرسٽ سرچ الگورٿم، جنهن کي breadth-first-searchBFS پڻ چيو ويندو آهي، ڏنو ويو آهي. ڪتاب هيٺ ڏنل گراف تي مشتمل آهي: ڪتاب ٻڌائي ٿو ته هڪ قطار اسان جي مدد ڪندي. ان کان علاوه، جيئن ته اسان عناصر کي آخر ۾ شامل ڪري سگھون ٿا ۽ قطار کي شروعات کان پروسيس ڪري سگھون ٿا. اهڙين قطارن کي انگريزي ۾ Two-way queues يا Deque چئبو آهي. ڪتاب هڪ ڊيٽا جي جوڙجڪ استعمال ڪرڻ جي صلاح ڏني آهي - هڪ هيش ٽيبل. نالو ۽ پاڙيسري سان تعلق رکڻ لاء. انگن اکرن سان، توهان صرف هڪ صف استعمال ڪري سگهو ٿا. چوڪن جي هن ذخيري کي ”لسٽ آف ڀرپاسي وارين چوڪن“ جي نالي سان سڏيو ويندو آهي، جنهن جو ڪتاب ۾ ذڪر نه ڪيو ويو آهي. اهو انهن لاء هڪ مائنس آهي. اچو ته ان کي جاوا ۾ لاڳو ڪريو:

private Map<String, String[]> getGraph() {
    Map<String, String[]> map = new HashMap<>();
    map.put("you", new String[]{"alice", "bob", "claire"});
    map.put("bob", new String[]{"anuj", "peggy"});
    map.put("alice", new String[]{"peggy"});
    map.put("claire", new String[]{"thom", "jonny"});
    map.put("annuj", null);
    map.put("peggy", null);
    map.put("thom", null);
    map.put("johny", null);
    return map;
}

هاڻي ڳولها پاڻ، هن ڊيٽا تي ٺهيل:

private String search() {
    Map<String, String[]> graph = getGraph();
    Set<String> searched = new HashSet<>();
    Deque<String> searchQue = new ArrayDeque<>();
    searchQue.add("you");
    while (!searchQue.isEmpty()) {
        String person = searchQue.pollFirst();
        System.out.println(person);
        if (personIsSeller(person)) {
            return person;
        } else {
            String[] friends = graph.get(person);
            if (friends == null) continue;
            for (String friend : friends) {
                if (friend != null && !searched.contains(friend)) {
                    searchQue.addLast(friend);
                }
            }
        }
    }
    return null;
}

جئين توهان ڏسي سگهو ٿا، ڪجھ به پيچيده ناهي. جيڪڏهن توهان ان جو مقابلو ڪتاب جي ڪوڊ سان ڪيو، اهو لڳ ڀڳ ساڳيو آهي.

گرافس، Dijkstra جي الگورتھم

BFS کي وڌيڪ يا گهٽ سمجھڻ سان، ڪتاب جو ليکڪ اسان کي دعوت ڏئي ٿو سمجھڻ لاءِ Daysktra algorithm ۽ weighted graphs. هيٺ ڏنل گراف حل لاء تجويز ڪيل آهي: پهرين، اسان کي سمجهڻ جي ضرورت آهي ته اسان جي گراف کي ڪيئن نمائندگي ڪجي. اسان ان کي ميٽرڪس جي طور تي نمائندگي ڪري سگهون ٿا. Habré تي ھڪڙو مضمون ھتي اسان جي مدد ڪندو: Dijkstra's algorithm. گراف تي بهترين رستا ڳولڻ . اچو ته ملائيندڙ ميٽرڪس استعمال ڪريون:

public Integer[][] getGraphMatrix(int size) {
    Integer[][] matrix = new Integer[size][size];
    matrix[0][1] = 6;
    matrix[0][2] = 2;
    matrix[2][1] = 3;
    matrix[1][3] = 1;
    matrix[2][3] = 5;
    return matrix;
}

۽ هاڻي منطق پاڻ:

@Test
public void dijkstra() {
    Integer[][] graph = getGraphMatrix();           // Данные графа
    Integer[] costs = new Integer[graph.length];    // Стоимость перехода
    Integer[] parents = new Integer[graph.length];  // Родительский узел
    BitSet visited = new BitSet(graph.length);      // "Ферма" маркеров посещённости

    Integer w = 0;
    do {
        System.out.println("-> Рассматриваем вершину: " + w);
        Integer min = null;
        for (int i = 0; i < graph.length; i++) {    // Обрабатываем каждую дугу
            if (graph[w][i] == null) continue;      // Дуги нет - идём дальше
            if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
                min = i;
            }
            if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
                System.out.print("Меням вес с " + costs[i]);
                costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
                System.out.println(" на " + costs[i] + " для вершины " + i);
                parents[i] = w;
            }
        }
        System.out.println("Вершина с минимальным весом: " + min);
        visited.set(w);
        w = min;
    } while (w != null);

    System.out.println(Arrays.toString(costs));
    printPath(parents, 3);
}

public void printPath(Integer[] parents, int target) {
    Integer parent = target;
    do {
        System.out.print(parent + " <- ");
        parent = parents[parent];
    } while (parent != null);
}

ڪتاب ان کي قدم بہ قدم ٽوڙي ٿو. جيڪڏهن توهان انٽرنيٽ تي Habré تي هڪ مضمون شامل ڪيو + ڪوڊ ڏسو، توهان ان کي ياد ڪري سگهو ٿا. مون ڏٺو ته قدم قدم جي تجزيي کي ٿورڙو بي ترتيب. پر قدم قدم جي فطرت لاءِ پاڻ هڪ پلس آهي. مجموعي طور تي، ٺيڪ، جيتوڻيڪ اهو بهتر ٿي سگهي ٿو)

لالچي الگورتھم

ايندڙ سيڪشن "لالچ الورورٿم" ڏانهن وقف آهي. هي سيڪشن دلچسپ آهي ڇاڪاڻ ته اهو سيٽ استعمال ڪري ٿو (java.util.Set). آخرڪار اسان ڏسي سگهون ٿا ته اهو ڇو ضروري آهي. اسان رياستن جي هڪ فهرست ان پٽ طور استعمال ڪندا آهيون:

Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));

۽ پڻ ريڊيو اسٽيشنن جي هڪ فهرست جيڪي انهن مان ڪجهه رياستن کي ڍڪيندا آهن:

Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));

ڪتاب پاڻ ڏانهن اشارو ۽ وضاحت ڪرڻ الورورٿم ڏانهن هلي ٿو:

Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
    String bestStation = null;
    Set<String> statesCovered = new HashSet();
    for (String station: stations.keySet()) {
        Set covered = new HashSet(statesNeeded);
        covered.retainAll(stations.get(station));
        if (covered.size() > statesCovered.size()) {
           bestStation = station;
           statesCovered = covered;
        }
    }
    statesNeeded.removeAll(statesCovered);
    finalStations.add(bestStation);
}
System.out.println(finalStations);

متحرڪ پروگرامنگ

ڪتاب پڻ انهن مسئلن کي بيان ڪري ٿو جن کي "متحرڪ پروگرامنگ" سڏيو ويندو آهي. ڪم ڏنو ويو آهي: اسان وٽ هڪ 4 lb بيگ آهي. توهان کي ڏنل وزن لاء سڀ کان وڌيڪ فائدي واري شيون ڳولڻ جي ضرورت آهي. پهرين، اچو ته شين جي هڪ فهرست ٺاهيو:

List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));

هاڻي الگورتھم پاڻ:

int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
    cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
    for (int j = 0; j < cell[i].length; j++) {
        // Если вещь не влезает - берём прошлый максимум
        if (things.get(i).weight > j+1) {
            cell[i][j] = cell[i - 1][j];
        } else {
            // Иначе текущая стоимость + предыдущий максимум оставшегося размера
            cell[i][j] = things.get(i).cost;
            if (j + 1 - things.get(i).weight > 0) {
                cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
            }
        }
    }
}
System.out.println(Arrays.deepToString(cell));

سڀ کان وڌيڪ ملندڙ لفظن کي ڳولڻ لاء پڻ هڪ دلچسپ ڪم آهي. دلچسپ، آهي نه؟ وڌيڪ تفصيل هتي: LongestCommonSubsequence.java

ويجهي پاڙيسري جي ڳولا ڪريو

ڪتاب پڻ تمام واضح طور تي k- ويجھي پاڙيسري الگورتھم بابت ڳالهائيندو آهي: ۽ حساب لاء فارمولا ڏنو ويو آهي:

هيٺين لائن

ڪتاب هڪ دلچسپ "اڳتي ڇا آهي؟" سيڪشن سان ختم ٿئي ٿو، جيڪو دلچسپ الگورتھم جو تڪڙو جائزو مهيا ڪري ٿو. هتي هڪ مختصر وضاحت آهي ته وڻن ۽ ٻين الگورتھم جي معني ڇا آهي. مجموعي طور، مون کي ڪتاب پسند ڪيو. ان کي سنجيدگيءَ سان نه ورتو وڃي جيئن ڪنهن قسم جي جامع معلومات. توهان کي پنهنجي لاءِ ڳولڻ ۽ سمجهڻو پوندو. پر جيئن دلچسپي جي تعارفي معلومات ۽ هڪ ابتدائي خيال ڏيو، اهو تمام سٺو آهي. ها، ڪتاب ۾ ڪوڊ پائٿون ۾ لکيل آهي. تنهن ڪري مٿين سڀني مثالن کي مرتب ڪيو وڃي ٿو) مون کي اميد آهي ته هي جائزو توهان کي اهو خيال حاصل ڪرڻ ۾ مدد ڪندو ته ڪتاب ۾ ڇا آهي ۽ ڇا اهو خريد ڪرڻ جي لائق آهي.

اضافي طور تي

توھان پڻ ھن موضوع تي ھيٺين وسيلن کي چيڪ ڪري سگھو ٿا:

1. EdX - جاوا پروگرامنگ جو تعارف: بنيادي ڊيٽا جي جوڙجڪ ۽ الگورتھم
2. LinkedIn - جاوا ۾ ڊيٽا جي جوڙجڪ ۽ الگورتھم جو تعارف (ادا ڪيل)
3. 27 سائيٽون پزل سان گڏ توھان جي پروگرامنگ صلاحيتن کي تيز ڪرڻ لاءِ
4. جاوا ڪوڊنگ بيٽ
5. پروگرامرز لاء ڪم، مختلف پيچيدگي جي ڪمن جا جواب

#وياچسلاو