我是编程新手。我可以找到由偶数组成的数字,但我的算法复杂度是 O(n)。对于大的
n
,我的算法太慢了。所以我需要一个更高效的算法。谁能帮我?
例如,第一个偶数数字是 0 , 2 , 4 , 6 , 8 , 20 , 22 , 24 , 26 , 28 , 40 等。 2686 是偶数数字的另一个例子。
这是我的代码:http://ideone.com/nsBzej
#include<bits/stdc++.h>
using namespace std;
long long int a[10],b[20];
long long int powr(int i)
{
long long int ans=5;
for(int j=2;j<=i;j++)
{
ans=ans*5;
}
return ans;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
long long int n,s,sum,p;
int t;
cin>>t;
for(int j=1;j<=t;j++)
{
s=20,sum=0;
a[1]=0, a[2]=2, a[3]=4, a[4]=6, a[5]=8;
for(int i=1;i<=17;i++)
{
b[i]=s;
s=s*10;
}
cin>>n;
for(int i=17;i>=1;i--)
{
p=powr(i);
while(p<n)
{
sum=sum+b[i];
n=n-p;
}
}
printf("Case %d: %lld\n",j,sum);
}
}
复杂度为O(n)。但我得到了错误的判决。
#include <stdio.h>
int main(void){
unsigned long long nth = 1000000000000ULL-1;//-1: 1 origin
unsigned long long k[30] = {0, 5};//28:Log10(ULL_MAX)/Log10(5) + 1
unsigned long long sum = k[1];
unsigned long long temp = 4;//4 : 2,4,6,8
int i;
//make table
for(i = 1; i < 30 ; ++i){
if(k[i] == 0){
temp *= 5;//5 : 0,2,4,6,8 , 2digits: 4*5, 3digits: 4*5*5
sum += temp;
k[i] = sum;
}
if(k[i] > nth)
break;
}
while(--i){//The same basically barakmanos
int n = nth / k[i];
printf("%d", n * 2);
nth -= n * k[i];
}
printf("%d\n", nth * 2);
return 0;
}
我们需要找到由 0、2、4、6 和 8 5 位数字组成的数字。 当我们将一个数字转换为基数 5 的数字时,它只会由数字 {0, 1, 2, 3, 4} 组成。 可以清楚地看出,所需的数字集合{0,2,4,6,8}中的每个数字都是5进制数字集合的相应索引中的数字的两倍。 因此,要找到仅由偶数组成的第 n 个数字,请按照以下步骤操作
步骤 1:将 n 转换为 n-1 这样做是为了排除零。 步骤 2:将 n 转换为 5 进制十进制数。 第三步:将上面找到的数字乘以2。这就是所需的数字
代码:
#include<bits/stdc++.h>
using namespace std;
int help(int n)
{
if (n == 1)
return 0;
vector< int> v;
n = n - 1;
while (n > 0)
{
v.push_back(n % 5);
n = n / 5;
}
int result = 0;
for (int i = v.size() - 1; i >= 0; i--)
{
result = result * 10;
result = result + v[i];
}
return 2*result;
}
// Driver Code
int main()
{
cout << help(2)
<< endl;
return 0;
}