تابع بازگشتی و رشته ای از اعداد

[CPPDeveloper]

سلام..

من به یک سوالی برخوردم و حل کردم،اما به جواب درست نرسیدم ( با توجه به جوابی که از قبل مشخص هست. )
و دقیقا نمی دانم مشکل کجاست..



The following iterative sequence is defined for the set of positive integers:
n http://projecteuler.net/images/symbol_maps.gif n/2 (n is even)
n http://projecteuler.net/images/symbol_maps.gif 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:

1 << 2 << 4 << 8 << 16 << 5 << 10 << 20 << 40 << 13
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.



در این سوال اگر عدد زوج بود تقسم بر دو می شود و اگر فرد بود ضرب در 3 و به علاوه 1 . و دوباره شرط بررسی می شود تا زمانی که به عدد یک برسیم..
هدف پیدا کردن عددی زیر یک میلیون که بزرگترین رشته را تولید کند.

من به عدد 910107 رسیدم با طول رشته 476. اما گویا جواب درست نیست!




int chain(int number,int& length)
{
length++;
int temp;
if (number<=1)
return 1;
else
{
if (number%2==0)
temp=chain(number/2,length);
else
temp=chain((3*number)+1,length);
}
return temp;
}


void problem14()
{
int length=0;
int max_length=length;
int max_length_number;

for (int i=999999; i>0; i--)
{
length=0;
chain(i,length);
cout<<i<<endl;
if (max_length<length)
{
max_length_number=i;
max_length=length;
}
}
　
cout<<"\nMax length number is: "<<max_length_number<<" Contains: "<<max_length<<" terms"<<endl;;
system("pause");
return;
}



با تشکر

[saber187518]

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

[Hadirj]

جواب درست چی هست حالا؟ من 837799 با طول 525 بدست آوردم اگه درسته بگو کد بزارم اما اصلا اوپتیمایز نیست :افسرده:

[CPPDeveloper]

با تشکر از دوستان به خاطر مشارکتشون..


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

رشته هم به این شکل تولید می شه که ، مثلا همون عدد 13: عدد 13 فرد هست بنابراین ضرب در 3 و به علاوه 1 می شه.. جواب می شه 40.. حالا دوباره عدد 40 زوج هست پس تقسیم بر دو می شه و جواب می شه 20 و همین عمل برای 20 هم تکرار می شه تا در نهایت به عدد یک برسیم... طول رشته ای که با این فرمول برای 13 تولید بشه 10 هست..

ما دنبال عددی هستیم که این بزرگترین رشته را داشته باشد.


جواب درست چی هست حالا؟ من 837799 با طول 525 بدست آوردم اگه درسته بگو کد بزارم اما اصلا اوپتیمایز نیست :افسرده:
بله درسته، جواب همینه...
لطفا بذارین ببینیم شما از چه راهی رفتین :-)



مشکل رو پیدا کردم... باید نوع int رو به long long تغییر می دادم:



long long chain(long long number,int& length)
{
length++;
long long temp;
if (number<=1)
return 1;
else
{
if (number%2==0)
temp=chain(number/2,length);
else
temp=chain((3*number)+1,length);
}
return temp;
}


void problem14()
{
int length=0;
int max_length=length;
long long max_length_number=0;

for (int i=999999; i>0; i--)
{
length=0;
chain(i,length);
cout<<i<<endl;
if (max_length<length)
{
max_length_number=i;
max_length=length;
}
}

cout<<"\nMax length number is: "<<max_length_number<<" Contains: "<<max_length<<" terms"<<endl;;
system("pause");
return;
}

[Hadirj]

بله درسته، جواب همینه...
لطفا بذارین ببینیم شما از چه راهی رفتین :-)


مشکل رو پیدا کردم... باید نوع int رو به long long تغییر می دادم:







#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
long long k;
long long counter=0;
vector<int> myvec;
vector<int> myvec2;
for (int i=1;i<1000000;i++){
k=i;
while(k>1){
if(k%2==0){
k=k/2;
}
else{
k=3*k+1;
}
counter++;
}
myvec.push_back(counter);
myvec2.push_back(i);
cout<<i<<" counter: "<<counter<<"\n";
counter=0;
}
int indexoflarrger;
vector<int>::const_iterator largest=max_element(myvec.begin(),myvec.end());
indexoflarrger=largest - myvec.begin();
cout<<"number of iterates: "<<(int) myvec[indexoflarrger] +1<< "\n";
cout<<"the number is: "<<(int) myvec2[indexoflarrger]<< "\n";
system("pause");
return 0;
}



یادم نیست اما فکر کنم بالای 10 دقیقه طول میکشه :اشتباه:

[sh4mid]

سلام

یادم نیست اما فکر کنم بالای 10 دقیقه طول میکشه

قسمت زیر را بردار تا اینقدر طول نکشه



cout<<i<<" counter: "<<counter<<"\n";

نیازی نیست cout یک میلیون بار فراخوانی بشه ، اینجا فقط باید جواب آخر رو به ما بده

[Hadirj]

سلام


قسمت زیر را بردار تا اینقدر طول نکشه



cout<<i<<" counter: "<<counter<<"\n";

نیازی نیست cout یک میلیون بار فراخوانی بشه ، اینجا فقط باید جواب آخر رو به ما بده

درسته! واسه این گذاشته بودم که ببینم درست کار میکنه یادم رفت پاکش کنم :لبخند: