论坛 › C\C++交流 › 各位大佬帮忙看道幂积序列的题目

耀耀切克闹 发表于 2022-4-20 22:36:05

各位大佬帮忙看道幂积序列的题目

本帖最后由 耀耀切克闹 于 2022-4-21 00:42 编辑

#include<stdio.h>
int pow(int a,int b)
{
        int i=1;
        if(b==0) a=1;
        else for(i=1;i<=b;i++)
        a*=a;
        return(a);
}
int main()
{
        int m,n;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
                int x=0,y=0,i=0,j=0,a;
                for(x=0;((pow(2,x))*(pow(3,y)))<n;x++)
                   for(y=0;((pow(2,x))*(pow(3,y)))<n;y++)
                          a=(pow(2,x))*(pow(3,y));
                printf("%d",i);
        }
        return 0;
}
设 x,y 为非负整数，试计算集合 M={(2^x)*(3^y),x>=0,y>=0} 的元素不大于指定整数 n 的个数，并求这些元素从小到大排序的第 m 项。

输入描述
多组输入，每组一行，输入 n 和 m，n 和 m 之间用一个空格分开

输出描述
对于每组输入，输出数列中不大于 n 的项数以及第 m 项的值，这两个数占两行。

样例输入：
10000000 100

样例输出：
190

93312

这道题我运行出来的结果很奇怪，但是我又不知道怎么改，查了网上的答案，是说要反过来思考，但是n很大的时候就运行不出来结果

wp231957 发表于 2022-4-21 09:13:28

本帖最后由 wp231957 于 2022-4-21 09:14 编辑

#include <stdio.h>

long long int mypow(int a,int b)
{
    long long int t=1;
    if(b==0)
      return 1;
    else
      for(int i=1;i<=b;i++) t*=a;
    return t;
}

int main()
{
    long long int m=10000000;
    int n=100;
    long long int result={0};
    int count=0;
    for(int i=0;1;i++)
    {
      for(int j=0;1;j++)
      {
            long long tmp=mypow(2,i)*mypow(3,j);
            if (tmp<=m)
            {
                result=tmp;
            }
            else
            {
                break;
            }
      }
      if (mypow(2,i)>m)
      {
            break;
      }
    }
    for (int i=0;i<count;i++)
    {
      for(int j=i+1;j<count;j++)
      {
            if (result>result)
            {
                int s=result;
                result=result;
                result=s;
            }
      }
    }
    printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result);
    return 0;
}

/*
PS C:\Users\Administrator> ./ct
共有190个数据满足要求，其中排序后第100个数据是 93312
*/

wp231957 发表于 2022-4-21 09:21:35

本帖最后由 wp231957 于 2022-4-21 09:24 编辑

代码可以简化一下，但是我觉得排序好像绕不过去
#include <stdio.h>

long long int mypow(int a,int b)
{
    long long int t=1;
    if(b==0)return 1;
    for(int i=1;i<=b;i++) t*=a;
    return t;
}

int main()
{
    long long int m=10000000;
    int n=100;
    long long int result={0};
    int count=0;
    for(int i=0;mypow(2,i)<=m;i++)
    {
      for(int j=0;mypow(2,i)*mypow(3,j)<=m;j++)
      {
            result=mypow(2,i)*mypow(3,j);
      }
    }
    for (int i=0;i<count;i++)
    {
      for(int j=i+1;j<count;j++)
      {
            if (result>result)
            {
                int s=result;
                result=result;
                result=s;
            }
      }
    }
    printf("共有%d个数据满足要求，其中排序后第100个数据是 %lld\n",count,result);
    return 0;
}

/*
PS C:\Users\Administrator> ./ct
共有190个数据满足要求，其中排序后第100个数据是 93312
*/

jhq999 发表于 2022-4-21 09:43:23

#include<stdio.h>
int pow(int a,int b)
{
      int i=1,s=1;
      if(b>0)
                        for(i=1;i<=b;i++)s*=a;
      return(s);
}
int main()
{
      int m,n;
               
       scanf("%d %d",&n,&m);
       int x=0,y=2,i=0,j=0,s=1,flag=1;
           for(x=0;flag;x++)
           {
                   flag=0;
                   for(y=0;(s=pow(2,x)*pow(3,y))<n;y++)
                   {
                           flag=1;
                           i++;
                           if(i==m) printf("%d\n",s);
                   }
           }
       printf("%d",i);
       
               
      return 0;
}

wp231957 发表于 2022-4-21 09:46:33

jhq999 发表于 2022-4-21 09:43


排序是咋绕过去的

耀耀切克闹 发表于 2022-4-21 09:49:31

wp231957 发表于 2022-4-21 09:46
排序是咋绕过去的

嗷嗷我想先把小于n的元素个数写出来的，但是结果不对嘛，排序还没写

傻眼貓咪 发表于 2022-4-21 10:18:06

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int f(int x, int y){
        return pow(2, x) * pow(3, y);
}

int compare(const void *a, const void *b){
   return *(int*)a - *(int*)b;
}

int main(){
        int
                n, m,
                count,
                a, b,
                N;
       
        scanf("%d%d", &n, &m);
       
        a = log2(n) + 1;
        b = log2(n) / log2(3) + 1;
        N = a*b;
       
        int arr;
       
        for(int i = 0; i < N; i++)
        arr = n+1;

        for(int x = 0, i = 0; x < a; x++){
                for(int y = 0; y < b; y++){
                        if(f(x, y) < n && f(x, y) > 0){
                                arr = f(x, y);
                        }
                }
        }
       
        qsort(arr, N, sizeof(int), compare);
       
        for(int i = 0; arr < n; i++){
                count = i + 1;
        }
       
        printf("%d\n\n%d", count, arr);
        return 0;
}

jhq999 发表于 2022-4-21 10:19:32

本帖最后由 jhq999 于 2022-4-21 10:23 编辑

wp231957 发表于 2022-4-21 09:46
排序是咋绕过去的

没想排序，只不过想测试下i==m时的值是否正确,估计是样例不具有普遍性
前面出来了，排序就简单了

查看完整版本: 各位大佬帮忙看道幂积序列的题目