کمک برای حل یک الگوریتم

[Ebrahim_T]

سلام به تمام دوستان برنامه نویس

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


مسله :

فرض می کنیم یک لیست داریم شامل تعدادی عدد
می خواهم بدونم حاصل جمع چند تا از این اعداد با هم برابر با عدد K می شود
به احتمال زیاد حالتهای مختلفی بوجود می اید برنامه بائد تمام حالتها را گزارش دهد

لطفا به من کمک کنید :cry:

با تشکر :flower:

[seyedof]

سلام
ر. ک. به الگوریتم انتخاب m شی از n شی که فکر کنم قبلا در این انجمن بررسی شده، اوونوقت میتونید برنامه رو بنویسید. یا اینکه حضور یا عدم حضور هر عضو لیست رو اگر یک بیت بگیرید اوونوقت باید یک عدد n بیتی رو در نظر بگیرید بعد از یک تا ۲ به توان n عدد رو تولید کنید، بعد در مبنای دو ببریدش اوونوقت در ازای بیتهای یک این عدد اوون عضو لیست رو به مجموع اضافه کنید تا ببینید حاصل جمع k هست یا نه...
ممنون علی

[Ebrahim_T]

سلام

خیلی ممنون که به سوال من جواب دادید

اما من زیاد متوجه نشدم :sorry:

بذارید یه مثال بزنم

فر ض می کنبم K=15 و لیست A شامل اعداد زیر باشد

A={1,3,4,7,9,10,2}

انگاه جوابها یصورت زیر است

1,3,4,7
1,4,10
3,2,10
4,9,2

و غیره

در ضمن برنامه باید تمام حالتها را پیدا کند

لطفا در حل این مسله به من کمک کنید

[esi022]

یه راه سادش استفاده از آرایه هست
من اینو نوشتم اما دم دستم ابزاری نیست که کام÷ایلش کنم حتی بیسیک
خودت تستش کن

<span dir=ltr>

var value:array[5] of string;

var a:array[5] of integer;



a[1]:=1;

a[2]:=3;

a[3]:=67;

a[4]:=6;

a[5]:=87;

k:=15;



for i := 1 to 5 do

begin

	test1=0

	for j:= 1 to 5 do

	if i=j then exit;

		begin

			test=test+a[i]+a[j]

			value[i]=value[i] + ' + ' + inttostr(j)

		end;

		if test<>K then  value[i]:=value[i] +' : False';

	end;

end;

for i=1 to 5 do

write value[i];

</span>

[Ebrahim_T]

سلام

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

لطفا اگر توانستید کاملتر توضیح دهید

با تشکر :flower:

در ضمن از دوستان دیگر خواهش می کنم به من در حل این مسله کمک کنند :flower:

[Ebrahim_T]

باز هم سلام

یعنی اینجا کسی نیست که بتونه کمک کنه

از همگی خواهش می کنم که یه عنایتی بکنند :cry:

با تشکر :(

[B-Vedadian]

سلام،

اگر تابع FloatToStr را برای تبدیل نوع اعداد حقیقی به رشته حرفی داشته باشی شاید برنامه زیر کمکت کند:

ایده این است که از میان تمامی زیرمجموعه های مجموعه اعداد داده شده، آنهایی را که مجموع اعضاشان برابر عدد دلخواه است چاپ می کند. این همان توضیح آقا/خانم Seyedof است.

const

  CMAX_NUMBERS=5;



function GetBit(N:Cardinal;n:Integer):I  nteger;

begin

  GetBit:=(N shr n) and 1;

end



var

  Number:array[1..CMAX_NUMBERS] of Extended;

  DesiredSum:Extended;



function CalcSum(N:Cardinal):Extended;

var

  i:Integer;

  Sum:Extended;

begin

  Sum:=0;

  for i:=0 to CMAX_NUMBERS-1 do

    Sum:=Sum+GetBit(N,i)*Number[i+1&#9  3;;

  CalcSum:=Sum;

end;



procedure PrintEqu(N:Cardinal);

var

  i:Integer;

  Sum:Extended;

  AStr:String;

begin

  AStr:=FloatToStr(DesiredSum)+'=';

  for i:=0 to CMAX_NUMBERS-1 do

    if GetBit(N,i)<>0 then

      AStr:=AStr+FloatToStr(Number[i+1]&  #41;+'+';

  if AStr[Length(AStr)]='+' then

    Delete(AStr,Length(AStr),1);

  writeln(AStr);

end;



var

  i:Cardinal;

begin

  for i:=1 to (1 shl CMAX_NUMBERS)-1 do

  begin

    if CalcSum(i)=DesiredSum then

      PrintEqu(i);

  end;

end;

[رضا جاسبی]

دوست عزیز آقا ابراهیم. برنامه ای که دوستمون B-Vedadian نوشته کامله ! فقط دو تا نکته رو در نظر بگیر.
1- مقدار دهی اولیه برای متغیر های Number و DesiredSum
2- نمی دونم در پاسکال این تابع FloatToStr کار می کنه یا نه. من قبلا پاسکال کار بودم. ولی فکر می کنم تابعی به نام Str داشته باشیم.
موفق باشی و لطفا نتیجه را اعلام کن.

[Delphi Skyline]

متشکرم

[Ebrahim_T]

سلام

یه دنیا تشکر :flower:

دست شما درد نکنه

اگه امکان داره یه مقدار در مورد منطق برنامه توضیح بدهید :oops:

با تشکر :D

[رضا جاسبی]

دوست من مساله بسیار ساده است. با عرض پوزش از B-Vedadian من توضیح می دهم.
در این روش تمام حالتهای ممکن بررسی می شود. فرض کن یک مجموعه n عنصری از اعداد داری. به چند حالت مختلف می توانی از این مجموعه یک زیر مجموعه ( در واقع انتخاب تعدادی از اعضا ) انتخاب کنی ؟ جواب دو به توان n است که در این راه حل با شیفت دادن به چپ عدد 1 به تعداد n یا همان CMAX_NUMBERS انجام شده است. حال برای بررسی هر کدام از این زیر مجموعه ها از تابع (CalcSum(N:Cardinal استفاده شده است که با یک چک ساده که آیا بیت متناظر با هر عنصر مجموعه وجود دارد یا خیر ، مجموع اعداد موجود در این زیر مجموعه محاسبه می شود و در صورتی که برابر مقدار درخواست شده بود چاپ می شود.
اگر باز هم مشکل داشتی توصیه می کنم مبحث زیر مجموعه ها ، نمایش بیتی اعداد و زیر مجموعه ها و همینطور عملگر های بیتی را مطالعه کنی.

[Ebrahim_T]

سلام

خیلی ممنون :flower:

کاملا متوجه شدم :D

با تشکر :موفق:

[frd]

×یشنهاد من اینه که از یه تابع بازگشثی استفاده کنی ما یه لیست با N
عنصر داریم که می خوایم همه زیرمجموعه های اونو که حاصل جمع اونامثلا x
میشه بدست بساریم
گام اولیه: اگر N==1 وعدد مورد نظر ما مساوی K بود عدد رو چا÷ کن
گام تکرار: for( i=1;i&lt;=N;i++)
exchenge(a[i],a[1])
function(i+1;N-1;k-a[i])

i اندیس آرایه از یک شروع میشه وهمیشه روی اندیسی که تااونجا بررسی شده
البته آلگوریتم رو اگه با اعدامثبت توی کل آرایه سروکار داشته باشیم میشه بهتر کرد مثلا هروقت مجموع بیشتراز Kشد دیگه بقیه حاتتها روبررسی نمی کنیم
exchenge همون جابه جاکردن//
:sunglass:

[Ebrahim_T]

:موفق:

[ramin2008]

کسایی که این ایده ها رو دادند خیلی کثیف برنامه نویسی میکنند.اصلا بهینه نیستند