第x大的数汉诺塔系列1 汉诺塔系列2

曾经终败给现在 2022-05-14 12:49 67阅读 0赞

#include<stdio.h>
    int a[100010];
    int f(int a[],int left,int right,int k)
    {
        int i ,j , x;
        x = a[left];
        i = left;
        j = right;
        while(i<j)
        {
            while(i<j&&a[j]<=x)
                j--;
            a[i] = a[j];
            while(i<j&&a[i]>=x)
                i++;
            a[j] = a[i];
        }
        a[i] = x;
        if(i==k)
            return a[k];
        else if(i>k)
          return f(a,left,i-1,k);
          else return f(a,i+1,right,k);
    }
    int main()
    {
        int i , n , m ,t,k;
        while(scanf("%d",&n)!=EOF)
        {
            for(i = 1;i<=n;i++)
                scanf("%d",&a[i]);
           scanf("%d",&t);
           while(t--)
         {
            scanf("%d",&k);
            m = f(a,1,n,k);
            printf("%d\n",m);
         }
        }
        return 0;
    }

第X大的数  
Problem Description  
X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 5) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。

Input  
多组输入。

每组首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。

Output  
输出N个数中第X大的数。

Sample Input  
41 2 2 341234  
Sample Output  
3221

汉诺塔系列1

Problem Description  
n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱子从下往上的大小仍保持如下关系 ：  
n=m+p+q  
a1>a2>…>am  
b1>b2>…>bp  
c1>c2>…>cq  
计算所有会产生的系列总数。

Input  
Normal07.8 磅02falsefalsefalseMicrosoftInternetExplorer4  
包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数目N<30。

Output  
Normal07.8 磅02falsefalsefalseMicrosoftInternetExplorer4  
对于每组数据，输出移动过程中所有会产生的系列总数。

Sample Input  
31329  
Sample Output  
32768630377364883

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    int  main()
    {
        int t;
        scanf("%d", &t);
        while(t--){
            int n;
            scanf("%d", &n);
            long long x;
            x = pow(3,n);
            printf("%lld\n", x);
        }
    
        return 0;
    }

汉诺塔系列2

Problem Description  
用1,2,…,n表示n个盘子，称为1号盘，2号盘,…。号数大盘子就大。经典的汉诺塔问  
题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于  
印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小  
顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱  
子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们  
知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘  
子总数和盘号，计算该盘子的移动次数.

Input  
包含多组数据，每组首先输入T,表示有T行数据。每行有两个整数，分别表示盘子的数目N(1<=N<=60)和盘号k(1<=k<=N)。  
Output  
对于每组数据，输出一个数，表示到达目标时k号盘需要的最少移动数。  
Sample Input  
2  
60 1  
3 1

#include <stdio.h>
    #include <stdlib.h>
      long long int  hannota(int N,int K)
      {
          if(K==N)  return 1;
          else   return hannota(N,K+1)*2;
      }
    int main()
    {
        int T,N,K,i;
        while(scanf("%d",&T)!=EOF)
        {
            for(i=1;i<=T;i++)
            {
                scanf("%d %d",&N,&K);
                printf("%lld\n",hannota(N,K));
    
            }
        }
        return 0;
    }

![这里写图片描述][70]

[70]: /images/20220514/dccd4789640c4026b111252cb10d2a61.png