کلاس HugeInteger

سلام . من کد اين کلاس رو مي خواستم . شايد همتون روشو بدونين . ولي باز هم من مي ذارم . ممنون ميشم کمکم کنين . اگه کد هم نذاشتين لطفا يه توضيحي بدين که قراره برنامه چيکار کنه . دو تا شي رو جمع کنه ؟ هر دو عدد بايد 40 رقمي باشه ؟ آخه اونوقت ضرب و جمعشون ممکنه بيش از 40 رقمي باشه . توابع input و output بايد چيکار کنن .

روي سوال :

کلاسي به نام HugeInteger ايجاد کنيد که از يک آرايه 40 عضوي از ارقام براي ذخيره اعداد صحيح 40 رقمي استفاده کند . توابع عضوي به نام هاي add , output , input و substract تدارک ببينيد . براي مقايسه اشياء HugeInteger توابعي به نام isEqualTo , isNotEqualTo , isGreaterThan , isLessThan , isGreaterThanOrEqualTo , isLessThanOrEqualTo بنويسيد که هر يک از اين ها ، تابعي گزاره اي هستند که اگر رابطه مورد نظر بين دو عدد صحيح بسيار بزرگ برقرار باشد true را بر مي گرداند و اگر اين رابطه برقرار نباشد false را برمي گرداند . تابعي گزاره اي به نام isZero بنويسيد . اگر علاقه مند هستيد توابع عضوي به نام هاي multiply , divide , modulus براي ضرب ، تقسيم و باقيمانده اعداد بسيار بزرگ بنويسيد .
:20:

برنامه زیاد سختی نیست اولش! اما وقتی بخواین تقسیم و اینها رو هم بنویسین سخت میشه. من توضیح میدم براتون شما هم سعی کنین خودتون بنویسین. اگه نتونستین که کد هم سعی می کنم بنویسم اگه وقت کردم! شما یه تابع input میذارین برای گرفتن اعداد. علت این که نمیشه از توابع معمولی c++ استفاده کرد این هست که با این توابع نمیشه بیشتر از 10 - 20 رقم رو گرفت. من دو تا روش پیشنهاد می کنم که هر کدوم رو خواستین می تونین ادامه بدین. یکیش این هست که عدد رو به صورت رشته بگیرین از کاربر. بعد از هر خونه آرایه 48 تا کم کنین و دونه دونه بذارین توی یه آرایه دیگه. روش دوم هم همینطوری هست فقط به جای این که بذارین توی یه آرایه دیگه از همون آرایه استفاده کنین. یعنی از هر خونه آرایه 48 تا کم کنین ( میدونین که چرا؟ )

توی تابع output هم دقیقا باید برعکس همین کار رو بکنین. یعنی آرایه جواب رو به صورتی چاپ کنین که کاربر به صورت عدد ببینه. میتونین همونطوری با cout به صورت خونه به خونه آرایه رو چاپ کنین یا اینکه که اول تبدیل کنین به یه رشته و بعد چاپ کنین.

تابع add یه تابع هست که توش یه آرایه 41 تایی باید بگیرین. علتش این هست که حاصل جمع دو تا عدد 40 رقمی حداکثر یه عدد 41 رقمی هست. یه متغیر دیگه هم میگیرین برای carry . یعنی برای جمع 9 و 8 عدد شما میشه 7 و carry میشه 1(همون که میگیم 1 بردست:31:) از i-1 شروع میکنین حلقه رو و کم میکنین یکی یکی. بعد اینطوری حساب میکنین:

کد:

---

ans[i+1]=num1[i] + num2[i] + carry;
carry = ans[i+1]/10;
ans[i+1]%=10;

---

و بیرون حلقه هم مینویسین:

کد:

---

ans[0]=carry;

---

همین.

برای تابع تفریق هم همینکارا رو می کنین تقریبا. یه خورده فرق میکنه. حتی می تونین از همین تابع add هم استفاده کنین برای تفریق. یه خورده فکر کنین روی این موضوع.

برای تابع ضرب باید یه آرایه 80 تایی بگیرین چون حاصل ضرب دو تا عدد n و m رقمی میشه n*m رقم حداکثر. این یه خورده سخت تر از بالایی ها هست اما می تونین با با یه خورده فکر بنویسین. باید از یه آرایه کمکی 41 تایی هم استفاده کنین ( فکر کنین ببینین چرا؟ ) باید یادتون باشه که موقع ضرب کردن رقم دوم باید یه صفر اضافه بشه به آخر عدد و موقع ضرب کردن رقم سوم دو تا صفر و .... خونه به خونه از آخر آرایه دوم شروع میکنین و به همه آرایه اول ضربش می کنین و میریزین توی آرایه کمکی. اگه مرحله اول بود که همینطوری با آرایه ans جمع میکنین و اگه مرحله دوم بود که یه صفر به آخرش اضافه می کنین و با ans جمع می کنین و همینطور تا آخر.

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

خيلي ممنون . پس تابع input و output همون ورودي خروجي هستن . تقريبا تابعهاي جمع و تفريق رو نوشته بودم . ولي اينطور که شما گفتين مثل اينکه تابع input پيچيده تر از جمع و تفريقه . قضيه 48 رو متاسفانه نفهميدم . (در مورد ورودي ها )
باز هم تشکر ...

نقل قول:

---

نوشته شده توسط sin2x=2sinxcosx [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

خيلي ممنون . پس تابع input و output همون ورودي خروجي هستن . تقريبا تابعهاي جمع و تفريق رو نوشته بودم . ولي اينطور که شما گفتين مثل اينکه تابع input پيچيده تر از جمع و تفريقه . قضيه 48 رو متاسفانه نفهميدم . (در مورد ورودي ها )
باز هم تشکر ...

---

وقتی شما عدد رو به صورت رشته از کاربر می گیرین یعنی هر خونه آرایه یه حرف هست. اگه بخوایم '0' رو که یه حرف هست به 0 که یه عدده تبدیل کنیم اون رو منهای 48 می کنیم چون کد اسکی صفر، 48 ه، واسه همین باید اگه 48 تا ازش کم کنیم میشه 0 عددی.

تابع input خیلی راحت تر از add و ایناست. شما یه آرایه کاراکتری اینطوری رو در نظر بگیرین:

کد:

---

char num1[40];

---

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

کد:

---

int number1[40]={0};
for (int i=39;i>=0;i--)
{
  number1[i]=num1[i]-48;
}

---

همین. حالا این آرایه رو میتونین به راحتی استفاده کنین. این که چرا از همون اول آرایه رو به صورت int نگیریم، علتش این هستش که اونطوری نمیشه با دستور مستقیم cin کل عدد رو یکجا گرفت. توی output هم دقیقا همین کار رو انجام میدیم فقط برعکسش رو. این کار رو هم انجام میدیم که آخرش بتونیم بنویسیم cout. فقط دقت کنین که باید آخر رشته رو با '0\' مشخص کنین.

نقل قول:

---

نوشته شده توسط m e h d i [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

وقتی شما عدد رو به صورت رشته از کاربر می گیرین یعنی هر خونه آرایه یه حرف هست. اگه بخوایم '0' رو که یه حرف هست به 0 که یه عدده تبدیل کنیم اون رو منهای 48 می کنیم چون کد اسکی صفر، 48 ه، واسه همین باید اگه 48 تا ازش کم کنیم میشه 0 عددی.

تابع input خیلی راحت تر از add و ایناست. شما یه آرایه کاراکتری اینطوری رو در نظر بگیرین:

کد:

---

char num1[40];

---

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

کد:

---

int number1[40]={0};
for (int i=39;i>=0;i--)
{
  number1[i]=num1[i]-48;
}

---

همین. حالا این آرایه رو میتونین به راحتی استفاده کنین. این که چرا از همون اول آرایه رو به صورت int نگیریم، علتش این هستش که اونطوری نمیشه با دستور مستقیم cin کل عدد رو یکجا گرفت. توی output هم دقیقا همین کار رو انجام میدیم فقط برعکسش رو. این کار رو هم انجام میدیم که آخرش بتونیم بنویسیم cout. فقط دقت کنین که باید آخر رشته رو با '0\' مشخص کنین.

---

از راهنمايي کاملتون خيلي خيلي متشکرم . مخصوصا در مورد اون 48 . خيلي لطف کردين مرسي . :20:

دوباره سلام . من فعلا يه قطعه از برنامه رو نوشتم . ولي اجرا نميشه . Syntax error نداره ها . بعد از وارد کردن عددها ديگه تابع output اجرا نميشه .


[html]
class HugeInteger
{
public:
HugeInteger ( );
void input ( );
void output ( );
void add ( HugeInteger *, HugeInteger * );
private:
int huge [ 40 ];
int arraySize;
};

//HugeInteger.cpp
#include <iostream>
#include "HugeInteger.h"
using namespace std;

HugeInteger::HugeInteger ( )
{
for ( int i = 0; i <= 39; i++ )
huge [ i ] = 0;
}

void HugeInteger::input ( )
{
char c [ 40 ];
cin.getline ( c, 40 );
arraySize = strlen ( c );
for ( int i = 0; i < arraySize; i++ )
huge [ i ] = c [ i ] - 48;
}

void HugeInteger::output ( )
{
cout << endl;
for ( int i = 0; i < arraySize; i++ )
cout << huge [ i ];
cout << endl;
}

void HugeInteger::add ( HugeInteger *h1, HugeInteger *h2 )
{
int s1 = h1->arraySize;
s1--;
int s2 = h2->arraySize;
s2--;
int m = 0;
int huge1 [ 40 ] = { 0 };
int huge2 [ 40 ] = { 0 };
int huge3 [ 41 ] = { 0 };
for ( int i = 0; i < s1; i++ )
huge1 [ i ] = h1->huge [ i ];
for ( int i = 0; i < s2; i++ )
huge2 [ i ] = h2->huge [ i ];
int x = 0;
while ( ( s1 == -1 ) && ( s2 == -1 ) )
{
m = huge1 [ s1 ] + huge2 [ s2 ] + m;
huge3 [ 40 - x ] = m % 10;
m /= 10;
s1--;
s2--;
if ( s1 == -1 )
for ( ; s2 > -1; s2--, x++ )
huge3 [ 40 - x - 1 ] = huge2 [ s2 ];
if ( s2 == -1 )
for ( ; s1 > -1; s1--, x++ )
huge3 [ 40 - x - 1 ] = huge1 [ s1 ];
x++;
}
int j = 0;
while ( j >= x )
{
huge3 [ j ] = huge3 [ 40 - j ];
j++;
}
for ( int k = x + 1; k <= 40; k++ )
huge3 [ k ] = 0;
arraySize = x;
}

//main.cpp
#include <iostream>
#include "HugeInteger.h"
using namespace std;

int main ( )
{
HugeInteger *h1 = new HugeInteger ( );
HugeInteger *h2 = new HugeInteger ( );
HugeInteger *h3 = new HugeInteger ( );
h1->input ( );
h2->input ( );
h3->add ( h1, h2 );
h3->output ( );
return 0;
}


[/html]

میشه تقسیم رو توضیح بدید؟

من قبلاً همچین جیزی نوشتم ولی زیاد رو تقسیم وقت نذاشتم.

الان کجکاو شدم بدونم.

مرسی.

نقل قول:

---

نوشته شده توسط sin2x=2sinxcosx [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

دوباره سلام . من فعلا يه قطعه از برنامه رو نوشتم . ولي اجرا نميشه . Syntax error نداره ها . بعد از وارد کردن عددها ديگه تابع output اجرا نميشه .

---

من کامل چک نکردم کد رو اما همینطوری که نگاه کردم گذرا مشکلی ندیدم داشته باشه. شاید هم کار میکنه! شما آخر تابع main یه getch() بذارین شاید درست بشه. اگه نشد بگین که چک کنم.

نقل قول:

---

میشه تقسیم رو توضیح بدید؟

من قبلاً همچین جیزی نوشتم ولی زیاد رو تقسیم وقت نذاشتم.

الان کجکاو شدم بدونم.

مرسی.

---

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

روش دوم همون الگوریتمی هست که ما موقع تقسم کردن ازش استفاده می کنیم. یعنی تقسیم رو به ضرب، تفریق و مقایسه تبدیل میکنیم. این روش، روش بدی نیست. به تعداد ارقام مقسوم علیه از مقسوم جدا میشه و باهاش مقایسه میشه. اگه تکه جدا شده از مقسوم علیه بزرگتر باشه که هیچی اگه نه یه رقم دیگه هم جدا میشه. برای قسمت ضربش متاسفانه من تا حالا روشی غیر از این روش که میگم به ذهنم نرسیده. چون ما نمی دونیم که باید به چند ضرب بشه تا از تکه جدا شده بزرگتر هم نشه و خیلی هم کوچیکتر نشه، میایم از یه جستجوی دودویی بین 1 تا 9 استفاده می کنیم. یعنی اول به 5 ضرب میکنیم و مقایسه و ... می کنیم و بعد مثلا به 8 یا 3 (طبق الگوریتم جستجوی دودویی) این قسمت الگوریتم زمان lg 10 رو داره( lg همون log در مبنای دو هست. ) این زمان با زمان الگوریتم ضرب، ضرب میشه و همچنین زمان الگوریتم مقایسه. زمان الگوریتم ضرب رو اگه n^2 بتونیم بکنیم( که بهتر از این هم میشه کرد) و زمان الگوریتم مقایسه رو تو بدترین حالت ممکن بذاریم n اونوقت این الگوریتم با n^3 * lg10 میشه که الگوریتم معقولی به نظر میرسه.

روشهای دیگه ای هم هستن که یه خورده سخته توضیح دادنشون دیگه. یکیش تبدیل تقسیم به ضرب و شیفت هست و اون یکی روش divide and conquer هست. اینها با زمانهای یه خورده بهتر از اینی که حساب کردم جواب میدن.

نقل قول:

---

نوشته شده توسط M E H D I [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

من کامل چک نکردم کد رو اما همینطوری که نگاه کردم گذرا مشکلی ندیدم داشته باشه. شاید هم کار میکنه! شما آخر تابع main یه getch() بذارین شاید درست بشه. اگه نشد بگین که چک کنم.

---

نه مشکل از اون نيست . من هيچ وقت از ()getch استفاده نمي کنم و برنامه هامو با CTRL + F5 اجرا مي کنم .

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

توی این کد که دارین input میکنین:

کد:

---

        for ( int i = 0; i < arraySize; i++ )
                huge [ i ] = c [ i ] - 48;

---

چرا آرایه رو از آخر پر نمی کنین که کارتون راحت تر بشه واسه مراحل بعد؟ توی برنامه شما هم که آرایه دینامیک استفاده نکردین لازم نیست اصلا از arraySize استفاده کنین به نظر من. حالا این که این امکان توی کلاس شما باشه خیلی خوبه.
کد پیشنهادی من این هست:

کد:

---

for(int i=39;i>=0;i--)
    huge[i] = c[i] -48;

---

توی این خطوط که از آبجکت h1 دارین آرایه رو کپی می کنین:

کد:

---

for ( int i = 0; i < s1; i++ )
                huge1 [ i ] = h1->huge [ i ];
        for ( int i = 0; i < s2; i++ )
                huge2 [ i ] = h2->huge [ i ];

---

آرایه huge شما توی کلاس HugeInteger یه آرایه 40 تایی هست و این آرایه Huge1 و Huge2 هم که ساختین 40 تایی هست. اگه آرایه رو به همون شکلی که چند خط بالاتر گفتم پر کنین می تونین از یه کدی مثل این استفاده کنین که راحت تر هم هست فهمش:

کد:

---

for (int i=0;i<40;i++)
{
    huge1[i] = h1->huge[i];
    huge2[i] = h2->huge[i];
}

---

توی این کد:

کد:

---

while ( ( s1 == -1 ) && ( s2 == -1 ) )

---

شرط ورود به حلقه شما همیشه false هست! باید == رو به =! تغییر بدین یا این که به جای اون بنویسین(قانون دمرگان):

کد:

---

while (! ( s1 == -1 ) || ( s2 == -1 ) )

---

بعد این که، ساختارتون برای جمع زدن یه خورده گنگ هست( حداقل من خیلی نفهمیدم ) چون عدد شما برای آرایه خیلی عدد کوچیکی هست ( 40 ) لازم نیست حتما کد رو بهینه بنویسین و به اندازه طول برین جلو. پیشنهاد من برای برنامه شما این هست که از آخر آرایه تا اولش با یه حلقه for برین.

کد:

---

for (int i=39;i>=0;i--)
{
    m=huge1[i]+huge2[i] + m;
    m/=10;
    huge3[i+1]=m%10;
}
huge3[0]=m;

---

ضمنا آرایه huge3 رو چون 41 تایی هست از خونه 40 پر می کنیم که این رو البته توی کد خودتون هم رعایت کردین. اگر هم از while میخواین استفاده کنین:

کد:

---

while( s1!=0 && s2!=0)
{
    m=huge1[i]+huge2[i] + m;
    m/=10;
    huge3[i+1]=m%10;
    s1--;
    s2--;
}
while(s1!=0)
{
    m=huge1[i]+ m;
    m/=10;
    huge3[i+1]=m%10;
}
while(s2!=0)
{
    m=huge2[i] + m;
    m/=10;
    huge3[i+1]=m%10;
}
huge3[0]=m;

---

while اول تا وقتی ادامه پیدا می کنه که یکی از عددها تموم بشن. بعد حلقه بعدی برای ادامه عدد دوم عمل جمع رو انجام میده. یه چیزی که شما توی کدتون بهش توجه نکردین این هست که این برنامه شما برای جمع 99999+1 دچار مشکل میشه. علتش این هست که عدد 1 زود تموم میشه توی حلقه اول و جواب میشه 0. اما واسه ادامه عدد 99999 دیگه m رو لحاظ نکردین. یعنی جواب این جمع با الگوریتم شما میشه 99990 و نه 100000. این قسمت کدتون منظورم هست:

کد:

---

huge3 [ 40 - x - 1 ] = huge2 [ s2 ];

---

بقیه کدتون مشکلی ندیدم من. باید اجرا بشه اصولا.

موفق باشید:46:

آقا خيلي لطف کردين . ممنون . برم توصيه هاي شما رو هم اعمال کنم ببينم چي ميشه . تو جمع اينقدر مشکل داشته باشم تو ضرب چيکار مي خوام بکنم !!