الگوریتمی ها جواب بدن

[hard engineer]

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

اگر بازم توضیح خواستین در خدمتم.(سوال ویرایش شد!!)

[mr.dp+]

سلام
اما هر چن تا گره داشته باشیم یه تله بیشتر نداریم.


خوب مگه هر گره نباید یک تله داشته باشه ؟

[a.r.khoshghalb]

سلا
الگوریتم ساده ای که منم به ذهنم میرسه همینیه که خودتون گفتین.
یعنی چی که "اما شرط توقف نمیشه براش تعیین کرد." ؟
یه متغیر روی لیستت حرکت میکنه هر جا به یه خونه ای رسید که قبلا دیده بودش اون خونه رو به عنوان خروجی بر میگردونه و برنامه تموم میشه.

[hard engineer]

سلا
الگوریتم ساده ای که منم به ذهنم میرسه همینیه که خودتون گفتین.
یعنی چی که "اما شرط توقف نمیشه براش تعیین کرد." ؟
یه متغیر روی لیستت حرکت میکنه هر جا به یه خونه ای رسید که قبلا دیده بودش اون خونه رو به عنوان خروجی بر میگردونه و برنامه تموم میشه.

انقدرام ساده نیست این مسله.وقتی بخوایم کد واسش بنویسیم باید از حلقه استفاده کنیم.شرط توقف واسه حلقه چی میشه؟اصن کدشو بنویسد

[a.r.khoshghalb]

انقدرام ساده نیست این مسله.وقتی بخوایم کد واسش بنویسیم باید از حلقه استفاده کنیم.شرط توقف واسه حلقه چی میشه؟اصن کدشو بنویسد

بدون استفاده از هر گونه داده ساختاری؟!
چه جوری ورودی سوال رو میگیرین؟ بگید من بقیه اش رو مینویسم.

[sa1378]

انقدرام ساده نیست این مسله.وقتی بخوایم کد واسش بنویسیم باید از حلقه استفاده کنیم.شرط توقف واسه حلقه چی میشه؟اصن کدشو بنویسد

صورت دقیق سوالتون با نوع ورودی و خروجیش بگین تا کد بزنیم

[hard engineer]

ورودیش که آدرس head لینک لیست هستش یعنی آدرس گره 1.یه لینک لیست خراب بش میدی باید درستش کنه.
لینک لیست خرابم که مشخصه دیگه.مثلن تو همین شکل سوال,گره 7 دات next,میشه گره 3.و همینجور گره 3 دات next,میشه گره 4 و .... تا دوباره برسه به گره 7.بعد از گره 7 دوباره 3 و الی آخر
میتونین برای تست کدتون خودتون یه لیست خراب بسازین. فقط کافیه آخرین گرهتون به دوباره به یکی از گره های وسط اشاره کنه و بیفته توی حلقه یا به اصطلاح تله.
خروجیشم که باید dataی گره ای که باعث خرابی شده رو برگردونه.تو عکس گره 7 باعث خرابی شده.چون به وجد آورنده ی تله شده.اگه گره 7 به جای اشاره به گره 3 به null اشاره میکرد تله ای نداشتیم.

[rahnema1]

این برنامه میتونه لیست را اصلاح کنه. تنها از یک متغیر به نام temp استفاده شده
فقط یک نکته وجود داره که تبدیل اشاره گر به عدد صحیح بستگی به پیاده سازی سیستم و کامپایلر داره و این برنامه در صورتی جواب درست میده که آدرس گره ها بین 0 تا 2 به توان 31 باشه

#include <iostream>
struct linkedlist
{
int value;
linkedlist * next;
};

void eslahelink(linkedlist * head)
{
if (sizeof(long long) / 2 >= sizeof(std::intptr_t))
{
//mark
linkedlist * temp = head;
while(1)
{
if((reinterpret_cast<long long>(temp -> next -> next)) < 0)
{
temp -> next = nullptr;
break;
}
temp -> next = reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp -> next));
temp = reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp -> next));
}
//recover
temp = head;
while(temp -> next != nullptr)
{
temp -> next = reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp -> next));
temp = temp -> next;
}
}
else
{
std::cout<< "Exit: Please compile with a 32 bit compiler!";
std::exit(1);
}
}

int main()
{
linkedlist * listarray[7];
for (int i = 0; i < 7; i++)
listarray[i] = new linkedlist;
for (int i = 0; i < 6; i++)
{
listarray[i] -> next = listarray[i+1];
listarray[i] -> value = i;
}
listarray[6] -> next = listarray[2];
listarray[6] -> value = 6;

linkedlist * head = listarray[0];
eslahelink(head);
while(head != nullptr)
{
std::cout << head -> value << std::endl;
head = head -> next;
}
}

[saeed410]

واسه خروج از حلقه میتونی از دستور break استفاده کنی. دستورات exit(0) و exit(1) هم هستند. که از برنامه خارج میکنه.C++

[Ananas]

این برنامه ( که تست نکردم؛ تستش به عهده شما) میتونه لیست را اصلاح کنه. تنها از یک متغیر به نام temp استفاده شده
فقط یک نکته وجود داره که تبدیل اشاره گر به عدد صحیح بستگی به پیاده سازی سیستم و کامپایلر داره

struct linkedlist
{
int value;
linkedlist * next;
};

int eslahelink(linkedlist * head)
{
if (sizeof(long long) >= sizeof(std::intptr_t))
{
linkedlist * temp = head;
while(1)
{
temp = reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp));
if(reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp)) -> next < 0)
{
temp -> next = nullptr
break;
}
temp = reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp)) -> next;
}
temp = head;
while(temp -> next != nullptr)
temp -> next = reinterpret_cast<linkedlist *>(~reinterpret_cast<long long>(temp -> next));
}
}

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

typedef struct TNode
{
public:
TNode()
{
Data = NULL;
Next = NULL;
};
void * Data;
TNode * Next;
} * PNode;

TNode * CheckList(TNode * p_node)
{
TNode * p_parent = p_node->Next;
if (p_parent == NULL)
{
return NULL;
}
else
{
p_node->Next = NULL;
TNode * result = CheckList(p_parent);
p_node->Next = p_parent;
if (result == NULL)
return p_node;
else
return result;
};
};

void RepairList(TNode * p_node)
{
TNode * p = CheckList(p_node);
if (p->Next->Next != NULL)
p->Next = NULL;
};

[rahnema1]

سلام.
امتحانش کردم، تموم نمیشد! برنامه رو بستم.
5 ساعت طول کشید تا یک راه حل به ذهنم رسید!!!!!!!!
اجرا کردم ظاهرا درسته.

سلام،بازم تشکر از شما حداقل یه نفر پیدا شد کد را اجرا کرد ببینه اجرا میشه یا نه.
کد خودم را اصلاح کردم به همرا برنامه تست گذاشتم بالا اما فقط وقتی به صورت 32 بیتی کامپیل بشه و آدرس گره ها بین 0 تا 2 به توان 31 باشه جواب می ده

در مورد کد شما روش جالبی بود. اگه بشه دو متغیر را تبدیل به یک متغیر کنید که خیلی عالی میشه :تشویق:

[hard engineer]

احسنت.شما در واقع هر گره رو با دات نکست = نال علامت گذاری میکنین
و لیست انقدر پیمایش میشه تا برسه به اولین نال.اولین نال همون دات نکست اولین گره حلفه هست.
عالی بود
این سوال تمرین ساختمان داده های استاد میرروشندل هست.دانشکاه گیلان.
تشکر

[Ananas]

کد خودم را اصلاح کردم به همرا برنامه تست گذاشتم بالا اما فقط وقتی به صورت 32 بیتی کامپیل بشه جواب می ده
اححححححححسنت. دستت دد نکنه. روش شما رو تازه الان متوجه شدم:لبخند:. خیلی جالبه:تشویق:.
با یک تغییر کوچیک مجبورش میکنیم که هم 32 هم 64 جواب بده:چشمک::

void eslahelink(linkedlist * head)
{
//mark
linkedlist * temp = head;
while(1)
{
if(
( ((size_t)temp->next->next) >> (sizeof(void *) * 8 - 1)) != 0
)
{
temp->next = NULL;
break;
};
temp->next = (linkedlist *)( ~((size_t)temp->next) );
temp = (linkedlist *)( ~((size_t)temp->next) );
}
//recover
temp = head;
while(temp->next != NULL)
{
temp->next = (linkedlist *)( ~((size_t)(temp -> next)) );
temp = temp->next;
};
};

تو این قسمت از شرط:

if(
( ((size_t)temp->next->next) >> (sizeof(void *) * 8 - 1)) != 0
)
اشاره گر رو تبدیل به عدد میکنیم بعد به تعداد سایز اشاره گر (میگزاریم کامپایلر خودش مشخص کنه) ضربدر 8 (هر بایت 8 بیت داره) منهای یک (بیت آخری بیرون نره چون دقیقا همونو لازم داریم) شیفت میدیم به راست. در واقع عدد منفی با این بیت آخر مشخص میشه.

احسنت.شما در واقع هر گره رو با دات نکست = نال علامت گذاری میکنین
و لیست انقدر پیمایش میشه تا برسه به اولین نال.اولین نال همون دات نکست اولین گره حلفه هست.
عالی بود
دقیقا. متشکر.

[rahnema1]

با یک تغییر کوچیک مجبورش میکنیم که هم 32 هم 64 جواب بده



الان که فکرش را می کنم، روشی که ارائه دادم کلا مشکل داره و فقط در موارد خاص جواب درست میده :خجالت: (مثلا در سیستم 32 بیتی مواقعی که آدرس گره های لیست بین 0 تا 2 به توان 31 باشه جواب درست میده)