黑马程序员技术交流社区

标题: 第五届蓝桥杯的一道题，当时没做出来，请大神指点一二... [打印本页]
作者: @追梦    时间: 2014-4-9 21:06
标题: 第五届蓝桥杯的一道题，当时没做出来，请大神指点一二...
本帖最后由 @追梦 于 2014-4-12 13:32 编辑

把abcd...s共19个字母组成的序列重复拼接106次，得到长度为2014的串。

    接下来删除第1个字母（即开头的字母a），以及第3个，第5个等所有奇数位置的字母。

    得到的新串再进行删除奇数位置字母的动作。如此下去，最后只剩下一个字母，请写出该字母。
作者: @追梦    时间: 2014-4-9 21:08
答案是 “q”，感觉还是没想出什么好的方法。
作者: zms2100    时间: 2014-4-9 23:08
占个位，找时间花个时间研究下，思考下编程要怎么弄。
作者: jingdou56    时间: 2014-4-10 02:13
本帖最后由 jingdou56 于 2014-4-10 03:38 编辑

不容易啊！
折腾出来了！

一不小心 折腾到这会儿了！

分享一下！

大家验证一下吧！

最后答案是 q !

睡觉了 ……

  1. class  TheLast
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 System.out.println("***********************华丽的分割线***********************");

  7.                 StringBuilder sb = new StringBuilder();
  8.                
  9.                 char[] c = new char[20];

  11.                 c[0] = 96;
  12.                
  13.                 for(int x = 1; x<=19; x++)
  14.                 {
  15.                         c[x] = (char)( c[x-1] + 1);
  16.                         sb.append(c[x]);
  17.                         System.out.print(c[x]);
  18.                 }
  19.                 System.out.println();


  22.                 String s = "";
  23.                 for(int y = 0; y<106;y++)
  24.                 {
  25.                         s = s + sb.toString() ;
  26.                 }
  27.                 System.out.println(s.length());
  28.                 System.out.println("***********************华丽的分割线***********************");

  30.                 String buil = getTheLast(s);

  32.                 while(buil.length() != 1)
  33.                 {
  34.                         buil = getTheLast(buil);
  35.                 }
  36.                
  37.                 System.out.println("最后的字母为：" + buil);
  38.         }

  40.         public static String getTheLast(String s)
  41.         {
  42.                 int flag;
  43.                 if(s.length() % 2 == 0)
  44.                         flag = 0;
  45.                 else
  46.                         flag =1;
  47.                 StringBuilder sb2 = new StringBuilder();

  49.                 while(s.length() != flag )
  50.                 {
  51.                         sb2.append(s.charAt(1));
  52.                         s = s.substring(2);

  54.                 }
  55.                
  56.                 return sb2.toString();
  57.         }
  58. }
复制代码







作者: 创造命运    时间: 2014-4-10 08:17
下面是我刚刚完成的，结果跟上面大神一样，也是q。

public class LanQiao
{
        public static void main(String[] args)
        {
                String str = "abcdefghijklmnopqrs";
                StringBuffer strbu = new StringBuffer();
                //StringBuffer strb = new StringBuffer("abcdefghij");
                //将字符串拼接106次
                for (int i = 0; i < 106; i++)
                {
                        strbu = strbu.append(str);
                }
               
                //按照题目的意思，删除字符串所有奇数位置的字母
                while (1 != strbu.length())  //最后剩下一个字母，故循环结束条件为最后的长度为1
                {
                        for (int i = 0; i < strbu.length(); i++)
                        {
                                //如果将字符串看成一个字符数组，那么按照题目的意思，就是删除数组中
                                //所有下标为偶数(包括0)的字母
                                strbu.deleteCharAt(i);  //删除索引i处的字母
                                //System.out.println(strb);
                        }
                }
                System.out.println(strbu);   //最后结果是q
        }
}


我用一个较短的字符串试了试，代码如下：
StringBuffer strb = new StringBuffer("abcdefghij");
while (1 != strb.length())  //最后剩下一个字母，故循环结束条件为最后的长度为1
{
        for (int i = 0; i < strb.length(); i++)
        {
                strb.deleteCharAt(i);  //删除索引i处的字母
                System.out.println(strb);
        }

}
编译运行后结果如下：

不知道大家注意到了没有，当你删除当前i处的字母时，后边的字母会向前移动一个字符，这样，当前已被删的字母的下一个字母其实已经移到i处了，但此时i已经自增了1。比如删除第一个字母a后，结果是bcdefghij,下一个要删除的是字母c。在for循环里，a被删除后，原来的strb变成了bcdefghij，而此时i自增1后的结果由0变为1，刚好是字母c的位置。由此可见，当删除一个字母后，后面的所有字母都会向前移动一位，然后i自增1，那么此时i所表示的位置刚好是下一次将要删除的字母。


有一个问题我没有弄明白。
在删除第一个字母a后，再次进行条件判断的时候， i < strb.length()，这里str.length()的结果是10呢，还是9。我试了一下，结果如下：


我奇怪的是，循环的时候，strb的长度一直在改变，为什么这里没有报异常：java.util.ConcurrentModificationException。
作者: 曲佳奇    时间: 2014-4-10 09:12
本帖最后由 曲佳奇 于 2014-4-10 11:41 编辑
  1. public class Test {
  2.     public static void main(String[] args) {
  3.         int[] a = new int[3000];
  4.         int tem,k,sum,p;
  5.         System.out.println("**输入字符串长度**");        
  6.         Scanner cin = new Scanner(System.in);
  7.         int num = cin.nextInt();
  8.         for(int i=1;i<num;i++)
  9.             a[i]=i;
  10.         k=0;  //标记不为0的数个数 当k=1时结束
  11.         tem=1;//每次间隔tem个数归零
  12.         sum=0;//记录结果
  13.         while(k!=1){
  14.             p=1;k=0;
  15.             for(int i=tem;i<num;i+=tem){
  16.                 if(p==0){
  17.                     p=1;
  18.                     continue;
  19.                 }else
  20.                     p=0;
  21.                 a[i]=0;
  22.             }
  23.             for(int i=1;i<num;i++){
  24.                 if(a[i]!=0){
  25.                     sum=a[i];
  26.                     k++;
  27.                 }
  28.             }
  29.             tem*=2;
  30.         }
  31.         sum = 'a' + sum % 19-1;
  32.         char c = (char) sum;
  33.         System.out.println(c);
  34.     }
  35. }
复制代码
由题目可知,每次执行删除操作后,第一个数都是2^n
在"2^n<给出数字<=2^n+1"这个范围内的数字删到最后时结果都为2^n
所以1024<2014<=2048
最后剩下的就是字符串的第1024位
作者: @追梦    时间: 2014-4-10 21:33
创造命运 发表于 2014-4-10 08:17
下面是我刚刚完成的，结果跟上面大神一样，也是q。

public class LanQiao

我说呢，删除下标为偶数的字母怎么不是  strbu.deleteCharAt(2i);而是strbu.deleteCharAt(i);，原来是它的长度一直在变化。。是不是因为StringBuffer是可变长度的字符串，所以才不会出现异常呢
作者: 小歪    时间: 2014-4-10 22:17


public class Test03 {
        public static void main(String args[])
        {
                int a[]=new int[2015];
                for(int j=1;j<=2014;j++)
                {
                        a[j]=j;
                }
                int i = 0;
                int num=2014;
                while (num/2!=0)
                {
                        for(i=1;i<num;i++)
                        {
                                if(i%2==0) a[i/2]=a[i];
                        }
                        num=num/2;
                }
                System.out.println(a[i/2]);
                System.out.println(a[i/2]%19);
               
        }

}
答案：Q  
看了下他们的算法都太复杂了没必要，此题只是考了个简单算法，楼主看看会有所感悟的，我是以123456...来代替abcde...   最后结果是17，也就是Q，很简单的算法。
作者: 小歪    时间: 2014-4-10 22:25
@追梦 发表于 2014-4-9 21:08
答案是 “q”，感觉还是没想出什么好的方法。

楼主看我的方法，会有所领悟。:loveliness:  晚安
作者: @追梦    时间: 2014-4-10 23:40
小歪 发表于 2014-4-10 22:25
楼主看我的方法，会有所领悟。  晚安

多谢，有所领悟，你的方法比较巧妙，我感觉是不是把最后两句改成System.out.println(a[1]);  System.out.println(a[1]%19);更容易理解些，你的程序相当于每次删除后把元素前移一半，直到最后一次，应该是a[1]存的既是要求的元素，你为什写的是a[i/2]呢，运行后 i 的结果为3，这点不太明白。。其实前面他们的算法只不过用的是可变长度字符串的一些方法，也不算复杂，哥们可以试着看看，方法也不错
作者: 小歪    时间: 2014-4-10 23:49
@追梦 发表于 2014-4-10 23:40
多谢，有所领悟，你的方法比较巧妙，我感觉是不是把最后两句改成System.out.println(a[1]);  System.out. ...

之所以a[i/2]是计算去掉奇数位后这些偶数位的新的坐标，其实楼主画个图假如只有10个字母自己亲自去奇数位操作一下，看看他们的下标变化就会更好理解的哦。
作者: 杨庆雷    时间: 2014-4-11 12:49
其实此题的思想就是:去掉奇数位,留下偶数位
比如说一组数:
        1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17
去除第一次余下的数为:
           2     4     6     8     10      12      14      16  都为2(也就是2^1)的倍数
去除第一次余下的数为:
                 4             8             12              16  都为4(也就是2^2)的倍数
去除第一次余下的数为:
                             8                             16  都为8(也就是2^3)的倍数
        ...............
也就是说去除n次后  最后剩下的一个数就是2的n的次数  那么去除多少次呢
剩下的最后一个数是要小于2014的 并且是2的次方的最大的数
2^n<2014<2^(n+1)  这个n就是我们需要的n

此题为例  n=10  也就是说 最后剩下的数 就是第2^10个数

(2^10)%19=17  也就是 Q         代码如下   
               
                        for(n = 0;Math.pow(2,n)< 2014;n++){                               
                        }
                        return n - 1;
                        得到n = 10

                        int m= Math.pow(2,n)%19
                        得到m = 17  也就是Q了
作者: 袁啟雄x    时间: 2014-4-11 14:46
本帖最后由 袁啟雄x 于 2014-4-11 16:15 编辑

我得答案也是Q - - 代码有点凌乱
  1. public class Demo {

  3.         public static void main(String[] args) {
  4.                 int size = 2014;
  5.                 char[] arr = new char[size];
  6.                 createArray(arr);
  7.                 swap(arr, size);
  8.         }
  9.         
  10.         public static void createArray(char[] arr){
  11.                 char c = 97;
  12.                 for (int i = 0; i < 2014; i++) {
  13.                         arr[i] = c++;
  14.                         if(c>115) c = 97;
  15.                         
  16.                 }
  17.         }
  18.         
  19.         public static void swap(char[] arr , int size){
  20.                 if(size==1){
  21.                         System.out.println(arr[0]);
  22.                         return;
  23.                 }
  24.                 int newSize = size;
  25.                 for (int i = 0; i < size; i+=2) {
  26.                         arr[i] = '\n' ;
  27.                         newSize--;
  28.                 }
  29.                 arr = swapArr(arr);
  30.                 swap(arr, newSize);
  31.         }
  32.         
  33.         public static char[] swapArr(char[] arr){
  34.                 char[] swapArr = new char[arr.length] ;
  35.                 int pos = 0 ;
  36.                 for (int i = 0; i < arr.length; i++) {
  37.                         if(arr[i]!='\n') swapArr[pos++] = arr[i];
  38.                 }
  39.                 return swapArr;
  40.         }

  42. }
复制代码
作者: Kelvinhu    时间: 2014-4-11 16:14
本帖最后由 Kelvinhu 于 2014-4-11 16:54 编辑

可以将问题简单化，把2014个字母放到数组中，其下标值最大2014-1（因为第一数组下标为0嘛）

数组的下标值是0   1   2   3  4  5  6  7  8  9  10  11  12.。。。。。。。。。。
第一次去除后就是  1       3       5     7      9        11       .。。。。。。。。。。
依次类推，这个规律就是 （2的n次方-1）  下标值 的数组就是最后一个的值的数组下标。
那么n是多少呢？可以用代码来算一下。
这个问题就简化成一个数组下标计算的问题。代码如下所示：
  1. class SimpleMath{
  2.        
  3.         public static void main(String args[]){
  4.                 System.out.print(getSquare());
  5.                 //由简单的规律可以得出 中间剩下的值就是2的（n-1）次方，那么它就是1024，这样取出第1024个数组的值即可。也就是下标数组[1024-1]的值
  6.         }
  7.        
  8.         static double getSquare(){
  9.                 //计算2014是2的多少次方？
  10.                 for(int i=0;;i++) {  
  11.                         if (2014==Math.pow(2,i)){
  12.                                 return i;
  13.                         }
  14.                 }
  15.         }
  16. }
复制代码


作者: ithmC4    时间: 2014-4-11 19:29
  1. class  StrDemo
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 String orgStr = "abcdefghijklmnopqrs";
  6.                 StringBuilder sb = new StringBuilder();
  7.                 for(int i=0; i<106; i++)
  8.                 {
  9.                         sb.append(orgStr);
  10.                 }
  11.                
  12.                 while(sb.length() != 1)
  13.                 {
  14.                         for(int i=0; i<sb.length(); i++) //难点在这个i++ 想通了一切都会明白
  15.                         {
  16.                                 sb.deleteCharAt(i);
  17.                         }
  18.                 }

  20.                 System.out.println(sb.toString());
  21.         }
  22. }
复制代码


输出结果是 q
作者: 诺忔。初禾、    时间: 2014-4-11 20:13
  1. public class demo {
  2.         static String str = "";
  3.         static StringBuffer sb;
  4.         static char c = 96;

  6.         public static void main(String[] args) {
  7.                 sb = new StringBuffer();
  8.                 creatString();
  9.                 deleteChar();
  10.                 System.out.println("result: " + str);
  11.         }

  13.         public static void creatString() {
  14.                 for (int i = 0; i < 106; i++) {
  15.                         for (int j = 0; j < 19; j++) {
  16.                                 c = (char) (c + 1);
  17.                                 sb.append(c);
  18.                         }
  19.                         c = 96;
  20.                 }
  21.         }

  23.         public static void deleteChar() {
  24.                 while (sb.length() > 1) {
  25.                         int i = 0;
  26.                         while (i < sb.length()) {
  27.                                 sb.deleteCharAt(i);
  28.                                 i++;
  29.                         }
  30.                 }
  31.                 str = sb.toString();
  32.         }
  33. }
复制代码
作者: 2528870651    时间: 2014-4-19 15:06
jingdou56 发表于 2014-4-10 02:13
不容易啊！
折腾出来了！

真不是人干的事，刚刚忙了30多分钟终于弄完了
  1. package it.cast;

  3. /*
  4. * 把abcd...s共19个字母组成的序列重复拼接106次，得到长度为2014的串。
  5. * 接下来删除第1个字母（即开头的字母a），以及第3个，第5个等所有奇数位置的字母。
  6. *得到的新串再进行删除奇数位置字母的动作。如此下去，最后只剩下一个字母，请写出该字母。
  7. * */
  8. public class MyTheLast {
  9.         public static void main(String[] args) {
  10.                 String str = "abcdefghijklmnopqrs";
  11.                 StringBuffer sb = new StringBuffer();
  12.                 for(int x =0 ; x<106; x++)
  13.                 {
  14.                         sb.append("abcdefghijklmnopqrs");
  15.                 }
  16.                 System.out.println(sb.length());

  18.                 System.out.println("最后一个字母为："+delete(sb));
  19.                
  20.                
  21.         }
  22.        
  23.         static StringBuffer delete(StringBuffer sb)
  24.         {
  25.                 StringBuffer sb1 = null;
  26.                
  27.                 do
  28.                 {
  29.                         sb1 = null;
  30.                     sb1 = new StringBuffer();
  31.                         for(int x = 0; x<sb.length()-1;x++)
  32.                         {
  33.                                 sb1.append(sb.charAt(x+1));
  34.                                 x++;       
  35.                         }
  36.                         String str2 = new String(sb1);
  37.                
  38.                         sb.replace(0, sb.length(), str2);
  39.                 }while( sb1.length()!=1 );
  40.                
  41.                 return sb1;
  42.                
  43.                
  44.         }

  46. }
复制代码
作者: wqqily    时间: 2017-12-5 00:34
用C做的{:8_472:}

#include <stdio.h>
#include <math.h>
void fun(char *ary,int i)
{
        int a,b,c;
        int z=1;
        if (i==1)
        {  printf("%c\n",ary[1]);
        }
        else            //记住是从零开始的。
           {
                   for(a=0;a<(i+1)/2;a++)
                   {
                           ary[a]=ary[z];
                           z+=2;
                   }
                   fun(ary,(i+1)/2);
           }
}
int main()         //应该是用递归。
{
   char ary[2014];
   int i,j,k=0;
   for(i=0;i<106;i++)
           for(j=97;j<116;j++)
       {
                   ary[k]=j; k++;
           }
   fun(ary,2013);
   return 0;
}



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2