گروکنگ الگورتھم یا الگورتھم کا بے درد تعارف

کتاب "گروکنگ الگورتھم" کا جائزہ۔ ایک چھوٹی سی ذاتی رائے، چند مثالیں۔ مجھے امید ہے کہ اس جائزے سے آپ کو یہ سمجھنے میں مدد ملے گی کہ آیا آپ اس کتاب کو پڑھنا چاہتے ہیں یا یہ آپ کے شیلف پر اپنی جگہ نہیں لے گی۔ انتباہ: بہت سارے متن)

"گروکنگ الگورتھم" یا الگورتھم کا بے درد تعارف

تعارف

تقریباً کسی بھی جونیئر لیول کی اسامی کے لیے "ڈیٹا ڈھانچے اور الگورتھم کا علم" جیسے تقاضے ہوتے ہیں۔ ان لوگوں کے لیے جن کے پاس خصوصی تعلیم ہے، الگورتھم کو عام کورس میں شامل کیا جاتا ہے اور کوئی مسئلہ نہیں ہونا چاہیے۔ لیکن کیا ہوگا اگر ترقی دوسرے میدانوں سے لائی جائے؟ جو کچھ باقی ہے وہ خود ہی سیکھنا ہے۔ اس سوال کا جواب موجود ہے کہ " قصور وار کون ہے" لیکن سوال "کیا کریں" کا جواب تلاش کرنا ہوگا۔ آئیے کتابوں میں دیکھتے ہیں۔ اور میں آپ کو ایک کے بارے میں بتانا چاہتا ہوں۔

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

تمام کاموں میں، میں نے "گروکنگ الگورتھم" جیسی کتاب دیکھی۔ آپ یہاں مزید جان سکتے ہیں: " کتاب "بڑھتے ہوئے الگورتھم۔ پروگرامرز اور متجسسوں کے لیے ایک واضح گائیڈ ۔" میں نے کتاب کو بہت پہلے دیکھا تھا، لیکن اوزون پر اس کی قیمت 680 روبل تھی۔ مہنگا یا سستا - ہر کوئی اپنے لئے فیصلہ کرتا ہے۔ میں پہلے ہی آدھی قیمت پر Avito پر دوسری کتاب خرید رہا ہوں۔ تو میں نے اسے سینٹ پیٹرزبرگ میں پایا، اسے خریدا، اور گروکنگ چلا گیا۔ جو میں نے آپ کے ساتھ شیئر کرنے کا فیصلہ کیا۔ جی ہاں، کتاب میں کوئی جاوا کوڈ نہیں ہے، لیکن وہاں ہے... دوسرا کوڈ، لیکن اس پر بعد میں مزید۔

الگورتھم کا تعارف (انتخاب کی ترتیب)

لہذا، بیان کی ایک آسان شکل میں، ہم اپنی کارکردگی میں پہلی ترتیب تک پہنچ جاتے ہیں۔ یہ سلیکشن کی ترتیب ہے۔ اس کا خلاصہ یہ ہے کہ ہم عناصر کو بائیں سے دائیں (0 عنصر سے آخری تک) سے گزرتے ہیں، اور باقی عناصر میں سب سے بڑے کو تلاش کرتے ہیں۔ اگر ہم اسے ڈھونڈتے ہیں، تو ہم اس عنصر کو تبدیل کرتے ہیں جس پر ہم اب ہیں اور سب سے بڑا عنصر۔ پہلے کسی صف کے بارے میں سوچنے کا آسان ترین طریقہ یہ ہے: [5، 3، 6، 2، 10]۔ کاغذ کا ایک ٹکڑا، ایک قلم (سب سے آسان اور سب سے سستا طریقہ) لیں اور تصور کریں کہ ہمارے پاس کس طرح بائیں بارڈر (بائیں)، موجودہ انڈیکس (یا دائیں بارڈر) ہے، کم از کم عنصر کا ایک اشاریہ موجود ہے۔ اور ہم اس کے ساتھ کیسے کام کرتے ہیں۔ مثال کے طور پر: الگورتھم کو اکثر سیڈوکوڈ میں بیان کیا جاتا ہے، مثال کے طور پر، ویکیپیڈیا پر۔ ہمارا بالکل سیڈوکوڈ نہیں ہے، لیکن اس پر بعد میں مزید۔ ابھی کے لیے دیکھتے ہیں:

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 سائز کا کھیت ہے۔ اس میدان کو برابر "مربع" میں تقسیم کرنا ضروری ہے۔ اور پھر اس کے بعد یوکلڈ الگورتھم کا ذکر ہے۔ جو مجھے پسند نہیں وہ یہ ہے کہ انہوں نے اس کا کوڈ لکھنے کی کوشش نہیں کی۔ لیکن یوکلڈ الگورتھم آسان اور موثر ہے: سچ پوچھیں تو، میں نے کتاب میں کچھ تفصیلات یاد کیں، جیسا کہ اس ویڈیو میں: " انفارمیٹکس۔ الگورتھم کا نظریہ۔ یوکلڈ کا الگورتھم ۔" مثال کے طور پر، اگر 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 شہر)، تو ہم ان میں سے n بنا سکتے ہیں! امتزاجات۔ آپ تکرار کے بارے میں یہاں مزید پڑھ سکتے ہیں: " تکرار۔ تربیتی کام ۔" تکراری اور تکراری طریقوں کا موازنہ: " تکرار "۔

فوری ترتیب

فوری ترتیب ایک دلچسپ الگورتھم ہے۔ کتاب اس کی طرف زیادہ توجہ نہیں دیتی۔ مزید یہ کہ، کوڈ صرف بدترین صورت کے لیے دیا جاتا ہے، جب پہلا عنصر منتخب کیا جاتا ہے۔ تاہم، شاید پہلے جاننے والے کے لیے یہ مثال یاد رکھنا آسان ہو گا۔ اور یہ بالکل بھی نہ لکھنے سے بہتر ہے کہ برا کوئیکسارٹ لکھیں۔ یہاں کتاب سے ایک مثال ہے:

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;
  }

  تفصیلات اوپر دیے گئے لنک پر۔ مختصر میں، ہم بائیں کرسر کو اس وقت تک منتقل کرتے ہیں جب تک کہ عنصر محور سے کم نہ ہو۔ اسی طرح، دائیں کرسر کو دوسرے سرے سے منتقل کریں۔ اور اگر کرسر مماثل نہیں ہوتے ہیں تو ہم تبادلہ کرتے ہیں۔ ہم اس وقت تک جاری رکھیں گے جب تک کہ کرسر آپس میں نہ مل جائیں۔ ہم ایک انڈیکس واپس کرتے ہیں جو مزید پروسیسنگ کو 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 کا نفاذ بھی ہے۔ اگر ہم ہیش ٹیبل ڈیوائس کو دیکھیں تو ہم دیکھیں گے کہ اندراج کی صف اندر رہتی ہے۔ اندراج ایک ایسا ریکارڈ ہے جو کلید - قدر کا مجموعہ ہے۔ ہیش ٹیبل میں ابتدائی صلاحیت ہے - یعنی ابتدائی سائز۔ اور لوڈ فیکٹر - لوڈ فیکٹر۔ ڈیفالٹ 0.75 ہے۔ یہ نمبر آپ کو بتاتا ہے کہ سرنی کے کس بوجھ پر (عناصر کی تعداد/کل تعداد) سائز کو بڑھانے کی ضرورت ہے۔ جاوا میں یہ 2 گنا بڑھ جاتا ہے۔ کتاب میں وضاحت کی گئی ہے کہ ہیش ٹیبلز کو ہیش ٹیبلز کہا جاتا ہے کیونکہ ہیش فنکشن کی بنیاد پر، سرنی سیل (ٹوکری) جس میں Entry. آپ یہاں مزید پڑھ سکتے ہیں: تصاویر میں ڈیٹا ڈھانچہ۔ HashMap اور LinkedHashMap ۔ آپ اسے کتابوں میں بھی پڑھ سکتے ہیں۔ مثال کے طور پر یہاں: " ہیش ٹیبل کی بنیادی باتیں "

گرافس، چوڑائی پہلی تلاش (مختصر ترین راستے کی تلاش)

شاید سب سے زیادہ دلچسپ موضوعات میں سے ایک گرافس ہے۔ اور یہاں، منصفانہ ہونا، کتاب ان پر بہت زیادہ توجہ دیتی ہے۔ شاید اسی لیے یہ کتاب پڑھنے کے قابل ہے۔ اگرچہ، شاید، یہ تھوڑا زیادہ واضح طور پر بیان کیا جا سکتا تھا)) لیکن، ہمارے پاس انٹرنیٹ ہے اور کتاب کے علاوہ، آپ نظریہ پر اس پلے لسٹ کو دیکھ سکتے ہیں "وہ لوگ جو پہلی بار گراف کے بارے میں سن رہے ہیں ۔ " ٹھیک ہے، قدرتی طور پر، کتاب کے بالکل شروع میں، چوڑائی-پہلی تلاش کا الگورتھم، جسے breadth-first-searchBFS بھی کہا جاتا ہے، دیا گیا ہے۔ کتاب مندرجہ ذیل گراف پر مشتمل ہے: کتاب میں کہا گیا ہے کہ ایک قطار ہماری مدد کرے گی۔ مزید یہ کہ اس طرح کہ ہم عناصر کو آخر میں شامل کر سکیں اور شروع سے ہی قطار پر کارروائی کر سکیں۔ ایسی قطاروں کو انگریزی میں دو طرفہ قطار یا 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 کو کم و بیش سمجھنے کے بعد، کتاب کا مصنف ہمیں ڈےسکٹرا الگورتھم اور وزنی گراف کو سمجھنے کی دعوت دیتا ہے۔ حل کے لیے درج ذیل گراف تجویز کیا گیا ہے۔ سب سے پہلے، ہمیں یہ سمجھنے کی ضرورت ہے کہ ہمارے گراف کی نمائندگی کیسے کی جائے۔ ہم اسے میٹرکس کے طور پر پیش کر سکتے ہیں۔ 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 پونڈ کا بیگ ہے۔ آپ کو دیئے گئے وزن کے لئے سب سے زیادہ منافع بخش اشیاء تلاش کرنے کی ضرورت ہے۔ سب سے پہلے، آئیے اشیاء کی فہرست بناتے ہیں:

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-قریب ترین پڑوسی الگورتھم کے بارے میں بھی واضح طور پر بات کی گئی ہے: اور حساب کا فارمولا دیا گیا ہے:

نیچے کی لکیر

کتاب ایک دلچسپ "آگے کیا ہے؟" سیکشن کے ساتھ ختم ہوتی ہے، جو دلچسپ الگورتھم کا فوری جائزہ فراہم کرتا ہے۔ یہاں ایک مختصر تفصیل ہے کہ درختوں اور دوسرے الگورتھم کا کیا مطلب ہے۔ مجموعی طور پر، مجھے کتاب پسند آئی۔ اسے کسی قسم کی جامع معلومات کے طور پر سنجیدگی سے نہیں لینا چاہیے۔ آپ کو اپنے آپ کو تلاش کرنا اور سمجھنا پڑے گا۔ لیکن دلچسپی کے لیے تعارفی معلومات کے طور پر اور ابتدائی خیال پیش کرنا، یہ کافی اچھا ہے۔ جی ہاں، کتاب میں کوڈ Python میں لکھا گیا ہے۔ لہذا مندرجہ بالا تمام مثالیں مرتب کی گئی ہیں) مجھے امید ہے کہ اس جائزے سے آپ کو یہ اندازہ لگانے میں مدد ملے گی کہ کتاب میں کیا ہے اور کیا یہ خریدنے کے قابل ہے۔

اضافی طور پر

آپ اس موضوع پر درج ذیل وسائل کو بھی دیکھ سکتے ہیں:

1. EdX - جاوا پروگرامنگ کا تعارف: بنیادی ڈیٹا سٹرکچرز اور الگورتھم
2. LinkedIn - جاوا میں ڈیٹا سٹرکچرز اور الگورتھم کا تعارف (ادائیگی)
3. آپ کی پروگرامنگ کی مہارت کو تیز کرنے کے لیے پہیلیاں والی 27 سائٹس
4. جاوا کوڈنگ بیٹ
5. پروگرامرز کے لیے کام، مختلف پیچیدگیوں کے کاموں کے جواب

#ویاچسلاو