Tree

[بمب منطقی]

با سلام خدمت دوستان:
من میخوام الگوریتم درختK تایی رو پیاده سازی کنم به طوری که هر گره دارای 4 گره فرزند باشه و به تعداد N ریشه عمق درخت باشه.
از دوستان خواهش میکنم تو این مورد به من کمک کنن.

[Sepidar]

تشکیل درخت بسته به مسائل مختلف فرق می کنه؛ اما به طور کلی کار خیلی شاقی نیست. اگه بیشتر توضیح بدی، کمک کردن هم ساده تر میشه. :موفق:

[بمب منطقی]

والا راستیتش من میخوام یکی از الگوریتم های FloodFill رو مخصوص پر کردن اشکال نا موزون رو پیاده سازی کنم. تا اینجاش رو فهمیدم که از یک درخت K تایی با 4 گره فرزند استفاده میکنه. به طوری که وقتی کاربر یک نقطه رو برای شروع کار پر کردن انتخاب میکنه(رنگ Border و Fill قبلا توسط کاربر انتخاب شده) اگه اون نقطه با رنگ Border انتخاب شده مخالف بود کار رو به این صورت ادامه بده که هر نقطه چهار نقطه اطراف خودش رو به همین صورت تست کنه(با این تفاوت که اگه با رنگ Fill هم برابر بود اون گره کارش تموم بشه) و هر نقطه(یا گره) وقتی برابر با شرط Border بود دیگه اون گره بسط داده نمیشه. مثل شکل زیرو چارت مربوطه.البته این فقط یک مثال وگرنه مقرون به صرفه نیست که اشکال منظم رو با این الگوریتم پر کنیم و مثلا باید از الگوریتم خطی برای این کار استفاده کنیم.
در شکل Color Border برابر آبی و Color Fill برابر مشکی و رنگهای قرمز نشون دهنده مواجه شده گره با Border Color و رنگ سبز نشان دهنده مواجه شدن گره با Fill Color.
در چارت هم بلوک های قرمز نشان دهنده مواجه شده گره با رنگ Border یا رنگ Fill.
امیدوارم تونسته باشم منظورم رو برسونم و انشالاه که تو شکل و Chart اشتباهی نکرده باشم.

[بمب منطقی]

بابا تو رو خدا یکی جواب بده

[Sepidar]

بمب عزیز! اگر هدفت واقعا فقط رنگ آمیزیه پیشنهاد من اینه که بی خیال درخت بشی و از یه الگوریتم باز گشتی ساده استفاده کنی. اما اگه واست ترتیب رنگ شدن مهمه، اونوقت بحث فرق میکنه.

[seyedof]

سلام
برای کار کردن با ساختارهای داده ای راحتترین روش استفاده از STL هست (اگه با زبان سی کار میکنید) STL=Standard Template Library توش برای درخت و لیست و پشته و... template های لازم رو داره. شما وقتی از درختش استفاده میکنید موقع ساختن درخت فقط ۴ تا فرزند بدین به هر گره.

فکر کنم میخواین برای FloodFill روشهای اول عمق Depth First و اول سطح Breadth First را آزمایش کنید.

ممنون علی

[بمب منطقی]

بمب عزیز! اگر هدفت واقعا فقط رنگ آمیزیه پیشنهاد من اینه که بی خیال درخت بشی و از یه الگوریتم باز گشتی ساده استفاده کنی. اما اگه واست ترتیب رنگ شدن مهمه، اونوقت بحث فرق میکنه.
آخه برای پر کردن اشکال نامنظم نمیشه از الگوریتمهای بازگشتی استفاده کرد. یا اگرم میشه من از اون خبری ندارم.

سلام
برای کار کردن با ساختارهای داده ای راحتترین روش استفاده از STL هست (اگه با زبان سی کار میکنید) STL=Standard Template Library توش برای درخت و لیست و پشته و... template های لازم رو داره. شما وقتی از درختش استفاده میکنید موقع ساختن درخت فقط ۴ تا فرزند بدین به هر گره.
والا من میخوام این ساختار رو تو دلفی(یا پاسکال فرقی نداره)پیاده سازی کنم.اگه تو دلفی یکچنین کتابخانه ای وجود داره منو بی خبر نزارین.
فقط میخواستم بدونم که یک درخت رو چطور میشه پیاده سازی کرد. تا اونجا که من میدونم با یه Link List میشه درخت رو پیاده سازی کرد. ولی چطوریش رو نمیدونم.
راستی چیزی که یادم رفت بگم اینه که تو شکل باید از بالا به پائین و از چپ به راست پیمایش کنید.
با تشکر :flower:

[بمب منطقی]

شما که فرمودید

تشکیل درخت بسته به مسائل مختلف فرق می کنه؛ اما به طور کلی کار خیلی شاقی نیست
پس چی شد.
بابا کسی نیست به من کمک کنه.من تا چند روز دیگه باید پروژه آخر دوره ام رو تحویل بدم که یکی از قسمتهاش اینه. کسی نمیتونه به من کمک کنه.
:(

[Sepidar]

conost
m,n=something;
var
pic:array[1..n,1..m]:TColor;
.
.
.
.
procedure paint(x,y:word;NewColor,BoundaryColor:TColor);
begin
if not((pic[x,y]=boundarycolor) or
(pic[x,y]=newcolor)) then begin

pic[x,y]:=newcolor;

paint(y-1,x ,newcolor,boundarycolor);
paint(y ,x+1,newcolor,boundarycolor);
paint(y+1,x ,newcolor,boundarycolor);
paint(y ,x-1,newcolor,boundarycolor);

end;
end;

خیلی بهینه نیست، اما فکر کنم کار کنه.

[بمب منطقی]

بهش نگاه کردم.نه متاسفانه این الگوریتم کار نخواهد کرد. چون تو این سطر گیر خواهد کرد

paint(y-1,x ,newcolor,boundarycolor);
همونطور که گفتم تو این الگوریتم نمیشه از تابع بازگشتی استفاده کرد چون تو این الگوریتم
ترتیب رنگ شدن مهمه،
پس اینطور که معلومه کار چندان راحتی نیست :wink:

[Sepidar]

type
PNode=^TNode;
TNode=Record
x,y:word;
P1,P2,P3,P4:PNode;
end;

const
m,n=something;
var
pic:array[1..n,1..m]:TColor;
.
.
.
.
function paint(xx,yy:word;NewColor,BoundaryColor:TColor):PN ode;
var
N:PNode;
begin
if not((pic[x,y]=boundarycolor) or (pic[x,y]=newcolor)) then
with N^ do begin
New(N);

x:=xx;y:=yy;
pic[xx,yy]:=newcolor;

P1:=paint(xx-1,yy ,newcolor,boundarycolor);
P2:=paint(xx ,yy+1,newcolor,boundarycolor);
P3:=paint(xx+1,yy ,newcolor,boundarycolor);
P4:=paint(xx ,yy-1,newcolor,boundarycolor);

paint:=n;
end
else paint:=nil;
end;
واقعا اگه اون یکی الگوریتم رو میگرفتی، تبدیلش واسه تشکیل درخت دیگه کاری نداشت.... :wink:

[Sepidar]

الگوریتم فوق به هیچ وجه بهینه نیست.الگوریتم بهینه احتمالا با استفاده از یک حلقه ساده (ساختار غیر بازگشتی) و یک پشته Bit Wise خواهد بود....

[بمب منطقی]

ثابت کردید که کار شاقی نیست :D
در هر صورت ممنون که همین رو هم در اختیار من گذاشتید.
با تشکر. :flower:

[seyedof]

سلام
آقاجان کاری نداره که!
اگر برای Algorithm Visualization میخوای یعنی نمایش نحوه کار کردن الگوریتم، اینطوری در نظر بگیر که هر پیکسل یک تصویر یک نود درخت یا گراف است که ۴ تا همسایه هاش در واقع ۴ تا بچه هاش هستند. بعدش که درخت رو ساختی میشه از روش DFS=Depth First یا BF=Breadth First این درخت رو پیمایش کنی.

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

ممنون علی

[بمب منطقی]

خیلی ممنون که وقتتون رو در اختیار من قرار دادید.مشکلم حل شده :) :flower:

[رضا جاسبی]

دوست من ! من نمی دونم که این الگوریتم چیه و چطور کار می کنه ولی برای درست کردن درخت شما باید یک Structure و یا یک Record در زبان پاسکال تعریف کنی. و چهار اشاره گر به همون نوع Record در اون تعریف باشه. من یک کمی ( خیلی یک کمی ! نزدیک به 7 سال ) هست که از پاسکال دورم. فکر کنم اشاره گر با علامت ^ تعریف می شه. من مدل C رو می نویسم خودت به پاسکال برگردون.


struct ListItem {
int A;
char b ;
... // Normal fileds you need
ListItem * Son1;
ListItem * Son2;
ListItem * Son3;
ListItem * Son4;
}

و هر عنصری رو که اضافه می کنی باید آدرسش رو در فیلد Son مربوطه در گره پدر قرار بدی.
لطفا نتیجه رو به من خبر بده.
موفق باشی

[بمب منطقی]

باشه حتما این رو امتحان می کنم . ولی شاید یه کم طول بکشه (مثلا1 یا 2 هفته بعد) چون یه کم سرم شلوغه.
باز هم ممنونم