PDA

View Full Version : کمک برای حل یک الگوریتم



Ebrahim_T
جمعه 16 بهمن 1383, 01:16 صبح
سلام به تمام دوستان برنامه نویس

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


مسله :

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

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

با تشکر :flower:

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

Ebrahim_T
شنبه 17 بهمن 1383, 01:44 صبح
سلام

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

اما من زیاد متوجه نشدم :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
شنبه 17 بهمن 1383, 04:51 صبح
یه راه سادش استفاده از آرایه هست
من اینو نوشتم اما دم دستم ابزاری نیست که کام÷ایلش کنم حتی بیسیک
خودت تستش کن

<span dir=ltr>
var value&#58;array&#91;5&#93; of string;
var a&#58;array&#91;5&#93; of integer;

a&#91;1&#93;&#58;=1;
a&#91;2&#93;&#58;=3;
a&#91;3&#93;&#58;=67;
a&#91;4&#93;&#58;=6;
a&#91;5&#93;&#58;=87;
k&#58;=15;

for i &#58;= 1 to 5 do
begin
test1=0
for j&#58;= 1 to 5 do
if i=j then exit;
begin
test=test+a&#91;i&#93;+a&#91;j&#93;
value&#91;i&#93;=value&#91;i&#93; + ' + ' + inttostr&#40;j&#41;
end;
if test&lt;>K then value&#91;i&#93;&#58;=value&#91;i&#93; +' &#58; False';
end;
end;
for i=1 to 5 do
write value&#91;i&#93;;</span>

Ebrahim_T
یک شنبه 18 بهمن 1383, 23:38 عصر
سلام

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

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

با تشکر :flower:

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

Ebrahim_T
چهارشنبه 21 بهمن 1383, 01:50 صبح
باز هم سلام

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

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

با تشکر :(

B-Vedadian
چهارشنبه 21 بهمن 1383, 09:33 صبح
سلام،

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

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



const
CMAX_NUMBERS=5;

function GetBit&#40;N&#58;Cardinal;n&#58;Integer&#41;&#58;Integer;
begin
GetBit&#58;=&#40;N shr n&#41; and 1;
end

var
Number&#58;array&#91;1..CMAX_NUMBERS&#93; of Extended;
DesiredSum&#58;Extended;

function CalcSum&#40;N&#58;Cardinal&#41;&#58;Extended;
var
i&#58;Integer;
Sum&#58;Extended;
begin
Sum&#58;=0;
for i&#58;=0 to CMAX_NUMBERS-1 do
Sum&#58;=Sum+GetBit&#40;N,i&#41;*Number&#91;i+1&#93;;
CalcSum&#58;=Sum;
end;

procedure PrintEqu&#40;N&#58;Cardinal&#41;;
var
i&#58;Integer;
Sum&#58;Extended;
AStr&#58;String;
begin
AStr&#58;=FloatToStr&#40;DesiredSum&#41;+'=';
for i&#58;=0 to CMAX_NUMBERS-1 do
if GetBit&#40;N,i&#41;&lt;>0 then
AStr&#58;=AStr+FloatToStr&#40;Number&#91;i+1&#93;&#41;+'+';
if AStr&#91;Length&#40;AStr&#41;&#93;='+' then
Delete&#40;AStr,Length&#40;AStr&#41;,1&#41;;
writeln&#40;AStr&#41;;
end;

var
i&#58;Cardinal;
begin
for i&#58;=1 to &#40;1 shl CMAX_NUMBERS&#41;-1 do
begin
if CalcSum&#40;i&#41;=DesiredSum then
PrintEqu&#40;i&#41;;
end;
end;

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

Delphi Skyline
چهارشنبه 21 بهمن 1383, 19:46 عصر
متشکرم

Ebrahim_T
یک شنبه 25 بهمن 1383, 00:40 صبح
سلام

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

دست شما درد نکنه :تشویق:

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

با تشکر :D

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

Ebrahim_T
دوشنبه 26 بهمن 1383, 01:56 صبح
سلام

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

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

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

frd
جمعه 05 فروردین 1384, 02:20 صبح
×یشنهاد من اینه که از یه تابع بازگشثی استفاده کنی ما یه لیست با 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
سه شنبه 09 فروردین 1384, 00:58 صبح
:موفق:

ramin2008
دوشنبه 31 اردیبهشت 1386, 10:59 صبح
کسایی که این ایده ها رو دادند خیلی کثیف برنامه نویسی میکنند.اصلا بهینه نیستند