مسئله دودویی با vector

[sa1378]

سلام
میخوایم با استفاده از vector این مسئله رو حل کنیم؟
چجوری میشه؟
مسئله:میخواهیم اعداد 1 تا n را در مبنای دو بدون فاصله پشت سرهم بنویسیم.
به طوری که هر عدد بتواند از ارقام عدد قبلی استفاده کند
مثلا برای n=3:
1011
اولین رقم 1 (از سمت چپ) برای عدد 1 (1)
برای عدد 2 تنها با گذاشتن صفر جلوی یک قبلی میتوان ان را ساخت (10)
برای عدد 3 نمیتوان از رقم های قبلی استفاده کرد پس مجبوریم دوباره انرا بنویسیم(11)

[a.r.khoshghalb]

راه خیلی ساده است.
اول در وکتورت عدد1 را میریزی، سپس، از روی خانه اول وکتور شروع به حرکت می کنی و هر خانه ای که دیدی را یکبار یکدونه یک جلوش اضافه می کنی و به وکتور اضافه می کنی یکبار یک دونه 0.
سیر تغیرات وکتور:
<1>
<1,10,11>
<1,10,11,100,101,110,111>
و...
سعی کن خودت کدشو بزنی اگر نتونستی بگو کمکت کنم...

[sa1378]

راه خیلی ساده است.
اول در وکتورت عدد1 را میریزی، سپس، از روی خانه اول وکتور شروع به حرکت می کنی و هر خانه ای که دیدی را یکبار یکدونه یک جلوش اضافه می کنی و به وکتور اضافه می کنی یکبار یک دونه 0.
سیر تغیرات وکتور:
<1>
<1,10,11>
<1,10,11,100,101,110,111>
و...
سعی کن خودت کدشو بزنی اگر نتونستی بگو کمکت کنم...

مثل اینکه منظورمو خوب نگفتم
برای n=3 جواب میشه ۱۰۱۱
برای I امین عدد که مینویسیم میتونیم از ارقام قبلی استفاده کنیم
مثلا برای I=2 که ۲ در مبنای دو میشه ۱۰ میتونیم از رقم ۱ قبلی که مال عدد ۱ بوده استفاده کنیم

[amirtork]

سلام
خوب، برای اینکار بیا اول باینری عددی رو که میخوای بزاری داخل وکتور در بیار، مثلا برای ۲ میشه ۱۰، حالا بیا تا اونجایی که رقم داخل وکتورت هست، با این چک کن، توی وکتور توی این مرحله ما فقط یه ۱ داریم، پس از مقایسه ی ۱۰ و ۱ جواب درست درمیاد، حالا باقی رقم هایی که از طول عدد باینری داخل وکتور بزرگتر بود رو اضافه کن، که توی اینجا صفر هست، حالا برای ۳، باینری عدد ۳ میشه، ۱۱، خب حالا میریم سراغ مقایسه کردن: توی وکتور چند رقم داریم؟ ۲ رقم: ۱۰، پس تا دورقم از عدد باینری که میخوایم بریزیم داخل وکتور رو باید مقایسه کنی که برای ۳ میشه: ۱۱، حالا از مقایسه ی ۱۱ و ۱۰ جواب نادرست(false)، پس باید کل رقم رو داخل وکتور push کنیم.
میدونم احتمالا خیلی بد توضیح دادم، اما تا اونجایی که الان به ذهنم رسیده باید درست جواب بده، فقط حواست باشه اگر تعداد رقم های داخل وکتور زیاد تر از تعداد رقم هایی که میخواستی مقایسه کنی بود، مقایسه رو تا انتهای ارقام وکتور انجام ندی! ران تایم ارور میگیری، یه شرط ساده بزار که از اونور عدد نزنی بیرون.
اگر دیدی خیلی بد توضیح دادم و نفهمیدی بگو، ایندفعه سعی میکنم واضح تر توضیح بدم.

[sa1378]

سلام
خوب، برای اینکار بیا اول باینری عددی رو که میخوای بزاری داخل وکتور در بیار، مثلا برای ۲ میشه ۱۰، حالا بیا تا اونجایی که رقم داخل وکتورت هست، با این چک کن، توی وکتور توی این مرحله ما فقط یه ۱ داریم، پس از مقایسه ی ۱۰ و ۱ جواب درست درمیاد، حالا باقی رقم هایی که از طول عدد باینری داخل وکتور بزرگتر بود رو اضافه کن، که توی اینجا صفر هست، حالا برای ۳، باینری عدد ۳ میشه، ۱۱، خب حالا میریم سراغ مقایسه کردن: توی وکتور چند رقم داریم؟ ۲ رقم: ۱۰، پس تا دورقم از عدد باینری که میخوایم بریزیم داخل وکتور رو باید مقایسه کنی که برای ۳ میشه: ۱۱، حالا از مقایسه ی ۱۱ و ۱۰ جواب نادرست(false)، پس باید کل رقم رو داخل وکتور push کنیم.
میدونم احتمالا خیلی بد توضیح دادم، اما تا اونجایی که الان به ذهنم رسیده باید درست جواب بده، فقط حواست باشه اگر تعداد رقم های داخل وکتور زیاد تر از تعداد رقم هایی که میخواستی مقایسه کنی بود، مقایسه رو تا انتهای ارقام وکتور انجام ندی! ران تایم ارور میگیری، یه شرط ساده بزار که از اونور عدد نزنی بیرون.
اگر دیدی خیلی بد توضیح دادم و نفهمیدی بگو، ایندفعه سعی میکنم واضح تر توضیح بدم.

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

[sa1378]

الان تنها سوالی که مونده اینه که این مقایسه چجوری کدش نوشته میشه؟:
122224

[rahnema1]

الان تنها سوالی که مونده اینه که این مقایسه چجوری کدش نوشته میشه؟:


خب شما تا جایی که می شه انجام داد کد را بذارید ( هر چند نصفه نیمه)

[sa1378]

خب شما تا جایی که می شه انجام داد کد را بذارید ( هر چند نصفه نیمه)

شاید کلا باید از یه راه دیگه رفت
int moghayese(vector <int> v1,vector <int> v2)
{
int p=0;
int v1n=(v1.size()-1);
int v2n=0;

while( v2n!=(v2.size()-1) )
{
if(v1n==v2n)
{
p++;
...
}

}
}

[a.r.khoshghalb]

اینکه با چه اوردری کار انجام بشه اهمیتی نداره؟ محدودیتی نیست؟

[sa1378]

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

[a.r.khoshghalb]

اگر اوردر اهمیتی نداره :

فرض کن جواب واسه n-1 تو وکتور v هست. و عدد n در مبنای دو توی وکتور binary.


int moghayese (vector<int> v, vector<int> binary)
{
int n = min(v.size(), binary.size());
int ans;
for (int i = 1; i <= n; i++)
{
bool flag = true;
for (int j = 0; j < i; j++)
{
if (binary[i] != v[v.size()-i-1])
{
flag = false;
break;
}
}
if (flag)
ans = i;
}
return ans;
}


توضیح:
ورودی تابع که مشخصه، خروجیش چیه؟ طول بزرگترین prefix از وکتور binary که یه suffix با همون طول توی وکتور v هست.
یعنی میگه چند رقم از اول عدد باینریت، در آخر وکتور v اومده.
مثلا به ازای این وکتور v و این وکتور binary:
v:
11100101001000100
binary:
10011100101000011
خروجی تابع میشه 3.

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

[sa1378]

یه سوال
چرا مقدار i از یک شروع میشه؟
پس[ binary[ 0 چی میشه؟
و اینکه از j توی حلقه اصلا استفاده نکردین و توی حلقه داخلی فقط i بار همون چیز تکرار میشه

[sa1378]

و یه چیز دیگه اینکه مقایسه ها باید اینطوری باشن:
binary[0],v[n]
اگه این درست بود:
binary[0],v[n-1]
binary[1],v[n]
اگه این دو تا درست بود:
binary[0],v[n-2]
binary[1],v[n-1]
binary[2],v[n]
و...
اگه اشتباه نکنم اشتباه متوجه شدین

من اصلا نمیتونم حلقه تودر تو بنویسم یا درست بفهمم
میشه یه راه حلی بگین؟
مثلا فایل آموزشی

[a.r.khoshghalb]

یه سوال
چرا مقدار i از یک شروع میشه؟
پس[ binary[ 0 چی میشه؟
و اینکه از j توی حلقه اصلا استفاده نکردین و توی حلقه داخلی فقط i بار همون چیز تکرار میشه

به خاطر 2 تا مسئله عذر می خوام!
یکی اینکه درسته از j استفاده نکردم! (به غلط!). هر دو بار از همون i استفاده شده. کد درست :

int moghayese (vector<int> v, vector<int> binary)
{
int n = min(v.size(), binary.size());
int ans;
for (int i = 1; i <= n; i++)
{
bool flag = true;
for (int j = 0; j < i; j++)
{
if (binary[j] != v[v.size()-j-1])

{
flag = false;
break;
}
}
if (flag)
ans = i;
}
return ans;
}




دومین معذرت خواهی بخاطر اینکه اصلا توضیح ندادم!
خوب
حلقه دوم که روی متغیر j هست میاد می بینه آیا i تا خونه اول وکتور binary با i تا خونه آخر وکتور v یکی هستند یا نه.
اگه یکی بودند i رو نگه میداره.
و i هم یکی یکی زیاد میشه.
یعنی i اول یکه، بعد می بینه اگر یک خونه اول binary با یک خونه آخر v برابر بود، i رو به عنوان جواب نگه می داره، بعد i رو یکی زیاد می کنه. بعد چک می کنه اگر دو خونه اول binary با 2 خونه آخر v یکی بود، i جدید رو به عنوان جواب نگه می داره و i رو یکی زیاد می کنه و روند ادامه داره...
یعنی دقیقا همون چیزی که شما اینجا گفتی:

binary[0],v[n]
اگه این درست بود:
binary[0],v[n-1]
binary[1],v[n]
اگه این دو تا درست بود:
binary[0],v[n-2]
binary[1],v[n-1]
binary[2],v[n]
و...

[sa1378]

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

[sa1378]

یه اشتباه بزرگشو فهمیدم
کدتون هنوز اشتباهه
توی این که به ازای i=2 مثلا
تو حلقه دومی میاد اول این دوتا رو مقایسه میکنه
binary[0],v[size-1]
بعد میاد این دوتارو میزنه
binary[1],v[size-2]
که این کاملا برعکسه و باید اینطوری باشه
binary[0],v[size-2]
binary[1],v[size-1]

که گیر اصلی کار هم از اول دقیقا همینجا بود

[sa1378]

این رو من کامل کدش رو نوشتم ولی فکر کنم چون مقایسه اشتباهه خروجی اشتباه میده
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//bargardandan addad mabna2
vector <int> mabna2(int n)
{
vector <int> vn;
while(n!=0)
{
vn.insert(vn.begin(),n%2);
n/=2;
}
return vn;
}
//bargardandan tedad argham moshtarak
int moghayese(vector <int> &v1,vector <int> &v2)
{
int n=min(v1.size(),v2.size());
int ans=0;
for(int i=1;i<=n;i++)
{
bool flag=true;

for(int j=0;j<i;j++)
{
if(v2[j]!=v1[v1.size()-j-1])
{
flag=false;
break;
}
}
if(flag=true)
ans=i;


}

return ans;

}
//ezafe kardan addad
void ezafe(vector <int> &v1,vector <int> &v2)
{
int k=moghayese(v1,v2);
for(int i=k;i<=(v2.size()-1);i++)
{
v1.push_back(v2[i]);
}

}
int main() {

vector <int> v1,v2;
int n=0;
cin>>n;
for(int i=1;i<=n;i++)
{
v2=mabna2(i);
ezafe(v1,v2);
}

//print ozv ha
for(int j=0;j<v1.size();j++)
{
cout<<v1[j] ;
}
cout<<endl;
return 0;
}

ورودی->1
خروجی->1
ورودی->2
خروجی->10
ورودی->3
خروجی->10
ورودی->4
خروجی->100

[a.r.khoshghalb]

بله اشتباه بود.
کد درست :

int moghayese (vector<int> v, vector<int> binary)
{
int n = min(v.size(), binary.size());
int ans = 0;

for (int i = 1; i <= n; i++)
{
bool flag = true;
for (int j = 0; j < i; j++)
{
if (binary[j] != v[v.size()-i+j])
{
flag = false;
break;
}
}
if (flag)
ans = i;
}
return ans;
}

[sa1378]

بله اشتباه بود.
کد درست :



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

[sa1378]

هنوز یه جای کد اشتباهه
خروجی اشتباه میده
تابع mabna2 مشکلی نداره چک شده
تابع ezafe هم که کارش سادست فکر نکنم مشکلی داشته باشه

vector <int> mabna2(int n)
{
vector <int> vn;
while(n!=0)
{
vn.insert(vn.begin(),n%2);
n/=2;
}
return vn;
}
//bargardandan tedad argham moshtarak
int moghayese(vector <int> &v1,vector <int> &v2)
{
int n=min(v1.size(),v2.size());
int ans=0;
for(int i=1;i<=n;i++)
{
bool flag=true;

for(int j=0;j<i;j++)
{
if(v2[j]!=v1[v1.size()-i+j])
{
flag=false;
break;
}
}
if(flag=true)
ans=i;


}

return ans;

}
//ezafe kardan addad
void ezafe(vector <int> &v1,vector <int> &v2)
{
int k=moghayese(v1,v2);
for(int i=k;i<=(v2.size()-1);i++)
{
v1.push_back(v2[i]);
}

}
int main() {

vector <int> v1,v2;
int n=0;
cin>>n;
for(int i=1;i<=n;i++)
{
v2=mabna2(i);
ezafe(v1,v2);
}

//print ozv ha
for(int j=0;j<v1.size();j++)
{
cout<<v1[j] ;
}
cout<<endl;
return 0;
}

[a.r.khoshghalb]

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

//bargardandan tedad argham moshtarak
int moghayese(vector <int> &v1,vector <int> &v2)
{
int n=min(v1.size(),v2.size());
int ans=0;
for(int i=1;i<=n;i++)
{
bool flag=true;
for(int j=0;j<i;j++)
{
if(v2[j]!=v1[v1.size()-i+j])
{
flag=false;
break;
}
}
if(flag == true)
ans=i;
}

return ans;

}