پیدا کردن کوچکترین مضرب مشترک بین اعداد یک تا بیست

می خواهیم کوچکترین مضرب مشترک بین اعداد یک تا بیست را پیدا کنیم . ساده ترین کار نوشتن برنامه ای است که در دو حلقه کار می کند . حلقه اول یکی یکی عدد را افزایش می دهد و حلقه دوم عدد ایجاد شده را به ترتیب بر 2 تا 20 تقسیم می کند و چنانچه باقیمانده همه تقسیم ها صفر شد به جواب مورد نظر دست یافته ایم . کد زیر این شیوه را پیاده سازی کرده است :

#!/usr/local/bin/perl
use strict;
use warnings;

my ($i, $div, $fl, $wl) = (0, 1, 0, 0);
my @list = (1..20);

while (1) {
	$i = $i + 1;
	$div = 1;
	$wl = $wl + 1;
	foreach my $j (@list) {
		# foreach loop counter
		$fl = $fl + 1;
		if ($i % $j != 0) {
			$div = 0;
			last;
		}
	}
	last if $div == 1;
}

print "The result is:$i\n";
print "=====================\n";
print "while loop counter: $wl\n";
print "foreach loop counter: $fl\n";

متغیر wl$ تعداد اعداد انتخاب شده جهت بررسی اینکه مضرب مشترک هستند یا نه را نشان می دهد و متغیر fl$  تعداد تقسیم های انجام گرفته جهت یافتن مضرب مشترک را نگهداری می کند.

عملکرد برنامه را به صورت زیر بررسی می کنیم:

# time perl maz.pl
The result is:232792560
=====================
while loop counter: 232792560
foreach loop counter: 648974546

real    7m9.363s
user    7m8.156s
sys     0m0.000s

مشاهده می کنید که برای رسیدن به جواب 232792560 عدد انتخاب شده و تعداد 648974546 تقسیم نیز صورت گرفته است . زمان اجرای این تکه کد 7 دقیقه است که به هیچ وجه قابل قبول نیست .

چگونه زمان اجرای برنامه را کمتر کنیم ؟

برنامه بالا بسیار ابتدایی و ساده است . اعداد را تک تک اضافه می کند و سپس اقدام به تقسیم عدد ایجاد شده بر اعداد 1 تا 20 می کند. نکات ساده زیر را در نظر بگیرید :

1. عددی بر 2 بخش پذیر است که رقم سمت راست آن زوج باشد یعنی می توانیم هنگام انتخاب عدد از روی اعداد فرد پرش کنیم و تعداد اعداد انتخابی تا جواب را نصف کنیم!
2. عددی بر 5 بخش پذیر است که رقم سمت راست آن 5 یا 0 باشد.  از انجایی که اعداد ما باید بر 2 هم بخش پذیر باشند یعنی زوج باشد پس سمت راست عدد ما می بایست منحصرا 0 باشد لذا می توانیم از روی 9 عدد پرش کنیم و مضرب بعدی 10 را انتخاب کنیم.
   
3. عددی بر 20 بخش پذیر است که سمت راست آن 00 یا 20 یا 40 یا 60 یا 80 باشد. لذا می توانیم هنگام انتخاب عدد به جای پرش از روی 9 عدد از روی 19 عدد عبور کنیم و مضرب بعدی 20 را انتخاب کنیم.

از روی نکته 3 تصمیم می گیریم اعداد را 20 تا 20 تا اضافه کنیم ولی چند مورد دیگر:

1. عددی که بر 20 بخش پذیر باشد بر 1 و  2 و 4 و 5 و 10 نیز بخش پذیر است . لذا چون عدد انتخابی ما قطعا مضرب 20 است پس مضرب این اعداد نیز می باشد. لذا این اعداد را از لیست تقسیم حذف می کنیم.
2. عددی که بر 14 بخش پذیر باشد بر 7 نیز بخش پذیر است لذا 7 را نیز از لیست تقسیم حذف می کنیم.
3. عددی که بر 16 بخش پذیر باشد بر 8 نیز بخش پذیر است لذا 8 را از لیست اعداد حذف می کنیم.
   
4. عددی که بر 18 بخش پذیر باشد بر 3 و 6 و 9 نیز بخش پذیر است. لذا این سه عدد را نیز از لیست تقسیم حذف می کنیم.

پس اعدادی که عدد مورد نظر ما باید بر آن ها بخش پذیر باشد عبارتند از:

11 12 13 14 15 16 17 18 19 20

کد برنامه را باز نویسی می کنیم :

#!/usr/local/bin/perl
use strict;
use warnings;

my ($i, $div, $fl, $wl) = (0, 1, 0, 0);
my @list = (11..19);

while (1) {
	$i = $i + 20;
	$div = 1;
	$wl = $wl + 1;

	foreach my $j (@list) {
		# foreach loop counter
		$fl = $fl + 1;
		if ($i % $j != 0) {
			$div = 0;
			last;
		}
	}
	last if $div == 1;
}

print "The result is:$i\n";
print "=====================\n";
print "while loop counter: $wl\n";
print "foreach loop counter: $fl\n";

و تست عملکرد برنامه جدید :

# time perl maz.pl
The result is:232792560
=====================
while loop counter: 11639628
foreach loop counter: 13086422

real    0m15.769s
user    0m15.724s
sys     0m0.000s

ملاحظه می فرمایید که زمان اجرای برنامه از 7 دقیقه به 15 ثانیه کاهش پیدا کرده است که فوق العاده خوب است . می توان باز هم به همین شیوه عملکرد برنامه را بهبود بخشید. مثلا اولین مضرب مشترک بین 15 و 18 عدد 90 است لذا می توان اعداد را به صورت مضارب 90 انتخاب کرد و دو عدد 15 و 18 را از لیست تقسیم حذف کرد . این عمل بر روی سیستم من زمان محاسبه را به 3 ثانیه تقلیل می دهد !

شاید بازی با اعداد به ما کمک کند تا رابطه های دیگری نیز بین این اعداد پیدا کنیم و محاسبه خود را سریعتر انجام دهیم ولی در حال حاضر من در چنین سطحی از ریاضیات قرار ندارم و احتمال بسیار زیاد هرگز نیز قرار نخواهم گرفت ! پس بهتر است برای حل مساله شیوه دیگری را نیز امتحان کنم !

جواب مساله ما قطعا مضربی از 20 می باشد لذا اعداد را 20 تا 20 تا اضافه می کنیم و بررسی می کنیم تا عدد انتخاب شده بر دو عدد اول لیست تقسیم بخش پذیر باشند . لیست تقسیم ما به صورت زیر است :

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

اولین عدد انتخابی ما 20 است که اتفاقا بر دو عدد اول لیست تقسیم ، بخش پذیر است . پس اولین عددی را پیدا کرده ایم که هم بر 20 و هم بر 1 و هم 2 بخش پذیر است لذا هر عدد دیگری که بر 1 و 2 و 20 بخش پذیر باشد می بایست مضربی از عدد انتخاب شده یعنی 20 باشند لذا هر سه عدد را از لیست حذف می کنیم و عدد انتخاب شده یعنی 20 را به آخر لیست تقسیم اضافه می کنیم . نسخه جدید لیست تقسیم به صورت زیر است :

[3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

ملاحظه می کنید که لیست تقسیم ما به اندازه دو عدد کوچکتر شده است . بار دیگر آخرین عنصر لیست تقسیم ( در اینجا 20 ) را در نظر می گیریم و به دنبال اولین مضربی از آن می گردیم که بر دو عدد اول لیست تقسیم ( در اینجا 3 و   4 ) بخش پذیر باشد . عدد 60 اولین مضرب 20 است که هم بر 3 و هم بر 4 بخش پذیر است . لذا هر عدد دیگری که هم بر 3 و هم بر 4 و هم بر 20 بخش پذیر باشد می بایست مضربی از عدد 60 باشد . پس هر 3 عدد 3 و  4 و 20 را از لیست خارج می کنیم و عدد 60 را به آخر لیست اضافه می کنیم. نسخه جدید لیست تقسیم به صورت زیر است :

[5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 60]

باز هم ملاحظه می کنید که لیست تقسیم به اندازه دو عدد کوچتر شده است . همین کار را تا زمانی که در لیست تقسیم تنها یک عدد وجود داشته باشد انجام می دهیم . آن یک عدد جواب مساله ماست .

چرا عدد پیدا شده ی جدید را در بالای لیست اضافه می کنیم ؟ در هر مرحله عدد مورد نظرمان را از انتهای لیست انتخاب می کنیم و سپس اقدام به یافتن مضربی از آن عدد می کنیم که بر دو عنصر اول لیست بخش پذیر باشند . مضربی که دارای این خصوصیت باشد طبیعتا از هر سه عدد اول و دوم و آخر لیست ( و طبیعتا تمام عناصر لیست تقسیم ) بزرگتر است . لذا بعد از حذف سه عدد نامبرده شده ( اعداد اول و دوم و آخر لیست تقسیم ) ، این عدد را به عنوان آخرین عنصر لیست تقسیم اضافه می کنیم تا در مرحله بعد مضارب این عدد مورد بررسی قرار بگیرند . این کار باعث پیشروی سریعتر ما به سمت جواب خواهد شد.

مراحل کامل تغییرات لیست تقسیم تا رسیدن به جواب در زیر نشان داده شده است :

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
[3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
[5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 60]
[7 8 9 10 11 12 13 14 15 16 17 18 19 60]
[9 10 11 12 13 14 15 16 17 18 19 840]
[11 12 13 14 15 16 17 18 19 2520]
[13 14 15 16 17 18 19 27720]
[15 16 17 18 19 360360]
[17 18 19 720720]
[19 12252240]
[232792560]

تکه کد پرل زیر این عملیات را پیاده سازی می کند :

#!/usr/local/bin/perl
#
# Find smallest multiple of 1 to 20
#
use strict;
use warnings;

my @arr = (1..20);

# loop counters: $owl, $iwl, $fl
my ($owl, $iwl, $fl, $i) = (0, 0, 0, 0);

print "[@arr]\n";

while (1) {
	last if $#arr == 0;
	$i = 0;
	$owl++;

	while (1) {
		$i += $arr[$#arr];
		$iwl++;
		my $div = 1;

		foreach my $j (@arr[0..1]) {
			$fl++;
			if ($i % $j != 0) {
				$div = 0;
				last;
			}
		}
		if ($div) {
			pop @arr;
			shift @arr;
			shift @arr;
			push @arr, $i;
			last;
		}
	}
	print "[@arr]\n";
}

print "=" x 52, "\nThe result is:@arr\n";
print "=======SUMMARY", "=" x 38 , "\n";
print "$owl  Times: Outer while loop\n";
print "$iwl  Times: Inner while loop\n";
print "$fl  Times: Foreach loop\n";

نتیجه اجرای این کد را ببینید :

# time perl maz2.pl
[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
[3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
[5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 60]
[7 8 9 10 11 12 13 14 15 16 17 18 19 60]
[9 10 11 12 13 14 15 16 17 18 19 840]
[11 12 13 14 15 16 17 18 19 2520]
[13 14 15 16 17 18 19 27720]
[15 16 17 18 19 360360]
[17 18 19 720720]
[19 12252240]
[232792560]
====================================================
The result is:232792560
=======SUMMARY======================================
10  Times: Outer while loop
84  Times: Inner while loop
96  Times: Foreach loop

real    0m0.008s
user    0m0.000s
sys     0m0.009s

ملاحظه می فرمایید که زمان اجرای برنامه به هشت هزارم ثانیه کاهش پیدا کرده است  . تعداد کل اعداد انتخاب شده جهت بررسی 84 عدد و تعداد تقسیم های صورت پذیرفته نیز 96 عدد می باشد که رقم بسیار کوچکتری نسبت به نسخه های اولیه برنامه می باشد .

نکته کوچک آنکه ابتدا برنامه perl را نوشتم و سپس اقدام به فلسفه بافی جهت توضیح برنامه کردم !