PDA

View Full Version : نوشتن الگوریتم تر کیب اعداد



maryam206
دوشنبه 17 شهریور 1382, 18:39 عصر
برنامه ای بنویسید که ترکیب یک سری اعداد ورودی را ایجاد کند و نمایش دهد.

Mashatan
سه شنبه 18 شهریور 1382, 00:59 صبح
اینو نوشتم ببینید درست کار میکنه
راستش در محیط دلفی نوشتم نمی دونستم با چه ساختاری راحترین
یک Memo و EDIT احتیاج داره



function Fact(n : int64) : int64;
var
i : integer;
begin
result := 1;
for i:=1 to n do
result := result*i;
end;

function Swap(st : string; n : Int64) : string;
var
nump : int64;
take : integer;
begin
nump := Fact(length(st)-1);
result := '';
repeat
take := ((n-1) div nump) + 1;
result := result + st[take];
Delete(st,take,1);
if (length(st) > 1) then
begin
n := ((n-1) mod nump)+1;
nump := nump div (length(st));
end;
until (length(St) = 1);
result := result + st;
end;

Procedure TForm1.Go;
var
i,j:Integer;
begin
Memo1.Lines.Clear;
j:=Fact(Length(Edit1.Text ));
for i:=1 to j do
Memo1.Lines.Add( Swap(inttostr(i)+' -> '+Edit1.Text,i));
end;

Kambiz
چهارشنبه 19 شهریور 1382, 01:55 صبح
جناب مشاطان لطف کردند و برنامه‌ای را به عنوان جواب ارائه کردند. اما چون پرسش در خصوص الگوریتم بود من از این فرصت استفاده میکنم و به تشریح این مسئله جهت یافتن الگوریتمی (متفاوت از آنچه آقای مشاطان ذکر کردند) به عنوان راه حل می‌پردازم.

----------------------------------------------------------------------------------------------------------

اگر قرار بود ترکیبهای (Permutations) موجود برای N عدد را بطور دستی بیابیم چه میکردیم؟ چند حالت را برای مقادیر مختلف N دنبال کنیم:

N = 0
خوب، در این حالت عددی وجود ندارد که بخواهیم ترکیبی بیابیم. :)

N = 1
فرض کنید که تنها عدد ما A باشد. بدیهی است که تنها می‌توانیم یک ترکیب بر روی کاغذ بیاوریم:

A

البته در این مورد باز صحبت خواهیم کرد!

N = 2
فرض کنید که اعداد ما عبارت باشند از A و B. در این حالت به دلخواه یک ترکیب را نوشته و سپس جای A و B را با هم عوض می‌کنیم:

A B
B A

N = 3
فرض کنید که اعدادمان A و B و C باشند. در این حالت ابتدا یکی از سه عدد را انتخاب کرده و روی کاغذ می‌نویسیم، به فرض A. سپس ترکیبات مختلف B و C را در مقابل آن می‌آوریم:

A B C
A C B

همین کار را با انتخاب B بعنوان عدد اول تکرار می‌کنیم:

B A C
B C A

و همچنین برای C:

C A B
C B A

خوب هر شش حالت ممکن را نوشتیم.

----------------------------------------------------------------------------------------------------------

اگر دقت کنید می‌بینید که روش یافتن ترکیبات حالت N = 2 را می‌توان با همان تعبیری که ترکیبات حالت N = 3 را یافتیم٬ بیان کنیم. بدین صورت که اول یکی از دو عدد را انتخاب کنیم و سپس تمام ترکیبات عدد دوم را که یکی بیش نیست (N = 1) در برابر آن بنویسیم و همین کار را با انتخاب عدد دوم تکرار کنیم.

حتی در مورد حالت N = 1 هم تعبیر بکار گرفته شده در مورد حالت N = 3 منطقی است. در این حالت تنها یک عدد برای انتخاب داریم و عدد دیگری در بین نیست (N = 0) که در برابر آن بنویسیم.

تنها در مورد حالت N = 0 است که نمی‌توان روش حالت N = 3 را به کار برد زیرا که چیزی برای یافتن وجود ندارد.

حال با این نتایج می‌توانیم روش یافتن ترکیبات n عدد را به صورت زیر بیان کنیم:

با قبول اینکه برای n برابر صفر هیچ ترکیبی وجود ندارد، برای بقیه حالات به ترتیب یکی از n عدد موجود را انتخاب کرده و ترکیبات n-1 عدد مابقی را در برابر آن قرار می‌دهیم.

روش بالا روشی است بازگشتی (Recursive) بدین معنا که برای تعریف آن مجددا از خود آن بهره گرفته‌ایم. تنها در حالت N = 0 است که تعریف متفاوت می‌باشد که آن را مبنای بازگشت (Recursive Base) می‌نامند.

اکنون که تعریفی از روش یافتن تمام ترکیبات مجموعه‌ای از اعداد ارائه دادیم، می‌توانیم آن را بطور الگوریتمیک و به کمک دو زیر روال بیان کنیم. یک زیر روال برای یافتن ترکیبات N عدد و دیگری انتخاب عددی که با انتخاب آن ترکیبات مابقی اعداد را در برابر آن قرار می‌دهیم.

----------------------------------------------------------------------------------------------------------

ترکیبات اعضای مجموعه‌ی S با تعداد N عضو را پیدا کن:
...... اگر N برابر صفر بود
............ مجموعه‌ی S را چاپ کن
...... در غیر این صورت
............ حلقه به ازای هر عضو از 1 تا N
.................. عنصر بعدی از مجموعه‌ی S با تعداد N عضو را عضو اول قرار بده
.................. ترکیبات اعضای مجموعه‌ی S با تعداد N-1 عضو را پیدا کن
............ پایان حلقه
...... پایان اگر
پایان روال


عنصر بعدی از مجموعه‌ی S با تعداد N عضو را عضو اول قرار بده:
...... <span dir=ltr>S(1) -> T</span>
...... حلقه به ازای i از 1 تا N-1
............ <span dir=ltr>S(i+1) -> S(i)</span>
...... پایان حلقه
...... <span dir=ltr>T -> S(N)</span>
پایان روال

----------------------------------------------------------------------------------------------------------

توجه داشته باشید که در هنگام چاپ مجموعه‌ی S باید کلیه اعضای آن را چاپ شوند نه فقط N عضو مشخص شده توسط پارامتر روال. نکته دیگر اینکه در این الگوریتم خاص به منظور بهینه‌سازی الگوریتم می‌توان مبنای بازگشت را به جای صفر٬ یک قرار داد.

S.Azish
سه شنبه 01 مهر 1382, 19:30 عصر
Option Explicit

Private Sub Form_Load&#40;&#41;
'
Dim orgNumbers&#40;6&#41; As Integer
Dim nNumbers&#40;&#41; As String
Dim i As Double


orgNumbers&#40;0&#41; = 1
orgNumbers&#40;1&#41; = 2
orgNumbers&#40;2&#41; = 3
orgNumbers&#40;3&#41; = 4
orgNumbers&#40;4&#41; = 5
orgNumbers&#40;5&#41; = 6
orgNumbers&#40;6&#41; = 7
'orgNumbers&#40;7&#41; = 8
'orgNumbers&#40;8&#41; = 9
'orgNumbers&#40;9&#41; = 0

nNumbers = CreateMultipleCases&#40;orgNumbers&#41;

List1.AddItem "Total numbers of cases&#58; " & UBound&#40;nNumbers&#41; + 1 ' which is I!

For i = 0 To UBound&#40;nNumbers&#41;
List1.AddItem nNumbers&#40;i&#41;
Next

'
End Sub

Private Function CreateMultipleCases&#40;eNumbers&#40;&#41; As Integer&#41; As String&#40;&#41;
'

Dim i As Byte
Dim a As Byte
Dim j As Double
Dim iItemsCount As Integer
Dim eNewNumbers&#40;&#41; As Integer
Dim eResult&#40;&#41; As String
Dim fResult&#40;&#41; As String
Dim iCounter As Double

iItemsCount = UBound&#40;eNumbers&#41; + 1


If iItemsCount > 1 Then 'For the last digit
ReDim eNewNumbers&#40;iItemsCount - 2&#41; As Integer

For a = 0 To iItemsCount - 1
Swap eNumbers&#40;0&#41;, eNumbers&#40;a&#41;
For i = 1 To iItemsCount - 1
eNewNumbers&#40;i - 1&#41; = eNumbers&#40;i&#41;
Next
eResult = CreateMultipleCases&#40;eNewNumbers&#41;
For j = 0 To UBound&#40;eResult&#41;
ReDim Preserve fResult&#40;iCounter&#41; As String
fResult&#40;iCounter&#41; = eNumbers&#40;0&#41; & eResult&#40;j&#41;
iCounter = iCounter + 1
Next
Next
Else
ReDim fResult&#40;0&#41; As String
fResult&#40;0&#41; = eNumbers&#40;0&#41;
End If

CreateMultipleCases = fResult
'
End Function

Private Sub Swap&#40;ByRef Number_1 As Integer, ByRef Number_2 As Integer&#41;
'
Dim tmpInt As Integer

tmpInt = Number_1
Number_1 = Number_2
Number_2 = tmpInt
'
End Sub

S.Azish
سه شنبه 01 مهر 1382, 19:30 عصر
Option Explicit

Private Sub Form_Load&#40;&#41;
'
Dim orgNumbers&#40;6&#41; As Integer
Dim nNumbers&#40;&#41; As String
Dim i As Double


orgNumbers&#40;0&#41; = 1
orgNumbers&#40;1&#41; = 2
orgNumbers&#40;2&#41; = 3
orgNumbers&#40;3&#41; = 4
orgNumbers&#40;4&#41; = 5
orgNumbers&#40;5&#41; = 6
orgNumbers&#40;6&#41; = 7
'orgNumbers&#40;7&#41; = 8
'orgNumbers&#40;8&#41; = 9
'orgNumbers&#40;9&#41; = 0

nNumbers = CreateMultipleCases&#40;orgNumbers&#41;

List1.AddItem "Total numbers of cases&#58; " & UBound&#40;nNumbers&#41; + 1 ' which is I!

For i = 0 To UBound&#40;nNumbers&#41;
List1.AddItem nNumbers&#40;i&#41;
Next

'
End Sub

Private Function CreateMultipleCases&#40;eNumbers&#40;&#41; As Integer&#41; As String&#40;&#41;
'

Dim i As Byte
Dim a As Byte
Dim j As Double
Dim iItemsCount As Integer
Dim eNewNumbers&#40;&#41; As Integer
Dim eResult&#40;&#41; As String
Dim fResult&#40;&#41; As String
Dim iCounter As Double

iItemsCount = UBound&#40;eNumbers&#41; + 1


If iItemsCount > 1 Then 'For the last digit
ReDim eNewNumbers&#40;iItemsCount - 2&#41; As Integer

For a = 0 To iItemsCount - 1
Swap eNumbers&#40;0&#41;, eNumbers&#40;a&#41;
For i = 1 To iItemsCount - 1
eNewNumbers&#40;i - 1&#41; = eNumbers&#40;i&#41;
Next
eResult = CreateMultipleCases&#40;eNewNumbers&#41;
For j = 0 To UBound&#40;eResult&#41;
ReDim Preserve fResult&#40;iCounter&#41; As String
fResult&#40;iCounter&#41; = eNumbers&#40;0&#41; & eResult&#40;j&#41;
iCounter = iCounter + 1
Next
Next
Else
ReDim fResult&#40;0&#41; As String
fResult&#40;0&#41; = eNumbers&#40;0&#41;
End If

CreateMultipleCases = fResult
'
End Function

Private Sub Swap&#40;ByRef Number_1 As Integer, ByRef Number_2 As Integer&#41;
'
Dim tmpInt As Integer

tmpInt = Number_1
Number_1 = Number_2
Number_2 = tmpInt
'
End Sub

Kambiz
شنبه 05 مهر 1382, 17:30 عصر
کد مربوط به الگوریتمی رو که قبلا" شرحش رو داده بودم به پاسکال اینجا می‌نویسم. دلیل اینکه اول ننوشتم برای این بود که فرصتی باشه تا خودتون الگوریتم رو کد کنید. و یک توضیح دیگه اینکه بجای آرایه‌ای از اعداد از آرایه‌ای از حروف استفاده شده تا علاوه بر ارقام بشه ترکیبات حروف رو هم بدست آورد.

ترکیبات اعضای مجموعه‌ی S با تعداد N عضو را پیدا کن:
...... اگر N کوچکتر یا برابر یک بود
............ مجموعه‌ی S را چاپ کن
...... در غیر این صورت
............ حلقه به ازای هر عضو از 1 تا N
.................. عنصر بعدی از مجموعه‌ی S با تعداد N عضو را عضو اول قرار بده
.................. ترکیبات اعضای مجموعه‌ی S با تعداد N-1 عضو را پیدا کن
............ پایان حلقه
...... پایان اگر
پایان روال


procedure Permutations&#40;var S&#58; String; N&#58; Integer&#41;;
var
I, J&#58; Integer;
Temp&#58; Char;
begin
if N &lt;= 1 then
Writeln&#40;S&#41;
else
for I &#58;= 1 to N do
begin
Temp &#58;= S&#91;1&#93;;
for J &#58;= 1 to N - 1 do
S&#91;J&#93; &#58;= S&#91;J + 1&#93;;
S&#91;N&#93; &#58;= Temp;
Permutations&#40;S, N - 1&#41;;
end;
end;

یک توضیح دیگه هم بدم که آرایه‌ای (رشته‌ای) که به این تابع فرستاده می‌شود بعد از برگشت تابع همان ترکیب اولیه را خواهد داشت.

shahmohammadi
یک شنبه 25 اردیبهشت 1390, 10:05 صبح
درك الگوريتم تركيب كمي سخته. براي همين برنامه تركيب رو يه تغيير كوچيكي دادم كه تو خروجي بشه فهميد كدوم چاپ مربوط به كدوم بازگشته. اميدوارم به دردتون بخوره.
#include <iostream.h>
#include <conio.h>

int l;
void perm(char *list,int i, int n)
{
l++;
for(int c=0;c<l;c++)
cout<<" ";
cout<<"{"<<i<<"-"<<n<<"\n";
int j;
char temp;
if (i==n)
{
for(c=0;c<=l;c++)
cout<<" ";
cout<<list<<endl;
//cout<<" ";
}
else
{
for(j=i;j<=n;j++)
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
perm(list,i+1,n);
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
for(c=0;c<l;c++)
cout<<" ";
cout<<"}\n";
l--;
}
void main()
{
clrscr();
perm("123",0,2);
getch();
}