悠然乱弹:挑战编程极限的问题终于有解了

  1. 云栖社区>
  2. 博客>
  3. 正文

悠然乱弹:挑战编程极限的问题终于有解了

悠悠悠然然 2016-05-09 14:54:10 浏览1241

问题的来历

在群里面一个小萝莉非要说拜我为师,呵呵,对于程序媛我一向--嗯嗯觉得程序不如人好看,再加上该名萝莉大学还没毕业,术语都多半没有听过,于是就想着拒绝,当时嘴一贱,就说了一句:你用一个For循环做个99表出来。

当然,这个对于小萝莉们来说,已经足够形成挑战了,但是对于群里的一众大佬们来说,自然是不在话下,3下5除二就搞定了。我又异想天开一下,如果不用判断语句,是不是也完成呢?粗想想是可以的,于是动手摆了几行代码,确实可以。于是就不断加码,不断增加新的完成条件,于是就形成了下面的问题,挑战极限这个定语,有一定的博眼球的意思,实际上不是那么难了。

挑战极限的问题

今天我想挑战一下OSCHINA的亲们的编程能力,出一道百度、谷歌不到答案的问题,第一个挑战成功的,直接奖励现金100元RMB(本人也是苦B码农,纯属意思一下)。

以前发过一条循环语句打印螺旋矩阵和蛇型矩阵的博客,今天我们来挑战只出现一条循环语句来打印99表。

注意,此题是考思想的,用“*”之外的运算符,如 "&  |  ^  >> << / % "的,虽然确实可以有解,但是代码逻辑与我倡导的:"一个好的算法首先是简单易懂的,其次是清晰明了的,再个一定是充满美感的"是相违背的。为什么下面条件这么多,实在是亲们的创意无限,我防不胜防哦。

特别声明:

  • n可以是任意正整数,只要N的平方不要溢出都可以
  • 一行一行print结果的无效
  • 不允许出现if,switch,?:语句及判断语句的变体,也就是只允许循环变量做条件比较以确定循环次数,不允许其它变量进行条件判断
  • 不允许出现异常
  • 循环语句中只能有一个变量
  • 代码行数超过100行的无效
  • 如果 @红薯 能抢先给出答案,奖金跃升为250元RMB
  • 提交问题并关注本人,回答才有效
  • 答案是否有效解释权归悠然所有

问题如下

不管是什么编程语言,只要是在程序中只用了一条循环语句正确的输出了99表,那么就算挑战成功。

下面是我的测试用例:

测试1:

public static void main(String[] args) {

        new Test99().print(9);

}

运行结果:

 1

 2 4

 3 6 9

 4 8 12 16

 5 10 15 20 25

 6 12 18 24 30 36

 7 14 21 28 35 42 49

 8 16 24 32 40 48 56 64

 9 18 27 36 45 54 63 72 81

测试2:

public static void main(String[] args) {

        new Test99().print(5);

}

运行结果:

 1

 2 4

 3 6 9

 4 8 12 16

 5 10 15 20 25

第一个回答正确的人将获得奖励,以时间为准。

攻城狮的答案

来自各种语言的攻城狮们,对偶的问题进行了长时间的轰炸,有的群大部分时间在讨论这个题有木有?半夜两点继续苦占的有没木有?避木不出的有没有(@红薯 ,别用帽子盖你的脑袋,偶看到你了)志有必得的有没有(工程的名字就叫GetMoney)?茶不思饭不香,没有思绪加班的有木有?

下面我们就一睹攻城狮们的风采:

利用语言特性搞定的

1
2
3
4
5
6
7
8
9
10
11
12
def main(row_count):
    for row_idx in range(1, row_count+1):
        row = map(lambda x:x*row_idx, range(1, row_idx+1))
        print(str(row)[1:-1].replace(",",""))
  
if __name__ == '__main__':
    print("-"*25)
    main(5)
    print("-"*25)
    main(9)
    print("-"*25)
    main(99)
这里有个技巧是 range(1, row_count+1):实际上是利用语言的特性来做了一个循环,不过,确实是非常简练的实现。

相当不错的Java版实现

1
2
3
4
5
6
7
8
9
10
11
12
13
<b> public static void print(int n){
            int i = 1;
            int j = 1;
            String flag[] = {"", "\n"};
            while(i <= n){
                System.out.print((i*j) + " ");
                int nextj = (j % i)+1;
                int nexti = (j / i) + i;
                System.out.print(flag[nexti - i]);
                i = nexti;
                j = nextj;
            }
        } </b>
这个实现也是非常不错的,唯一的就是利用了"%  /"小小的违规了一把,而且非常漂亮的把if语句给回避了-实际上是转换成上数组下标了。

依然不错的Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<b>public class MultiplicationTable2 {
  
    int line = 1;
    int cursor;
  
    public void print(final int maxLine) {
  
        for (cursor = 1; cursor <= line || enter() <= maxLine; cursor++) {
            System.out.print(cursor * line + "\t");
        }
  
    }
  
    public int enter() {
        System.out.print("\n");
        line++;
        cursor = 1;
        return line;
    }
  
    public static void main(String[] args) {
        new MultiplicationTable2().print(9);
    }
  
}</b>
这个实现的也非常不错,唯一违规的地方是在For语句中夹带了判断语句。

一个for里面搞两个循环变量的

1
2
3
4
5
6
7
8
9
<b>for (int i = 1, j = 1; j <= 9; i++)
    {
     System.out.printf("%d*%d=" + i * j + " ", i, j);
     if (i == j) {
      i = 0;
      j++;
      System.out.println();
     }
    } </b>
当然,里面还多一个if判断

一不小心用了两个For的解法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package everydaydo;
 
 
public class OSC {
 
 
public static void main(String[] args) {
OSC.fun1(9);
}
 
 
public static void fun1(int n){
StringBuilder sb = new StringBuilder();
for(int i=1;i<=n;i++){
sb.append(fun2(i));
}
System.out.println(sb.toString());
}
 
public static String fun2(int m){
StringBuilder sb = new StringBuilder();
for(int i=1;i<=m;i++){
sb.append(i*m+"\t");
}
sb.append("\n");
return sb.toString();
}
}

有把历史实现直接过过冲奖的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class MulTable{
    public enum MulTableEnum{
        ASC,
        DESC
    }
    public void showMulTable(final int count, MulTableEnum e){
        if(MulTableEnum.ASC == e){
            ascMulTable(count);
        }else{
            descMulTable(count);
        }
    }
    private void descMulTable(final int count){
        if(count<1){
            i=0;
            return;
        }
        if(i!=count){
            i++;
            System.out.print(i+"*"+count+"="+i*count+"\t");
            descMulTable(count);
        }else{
            i=0;
            System.out.println();
            descMulTable(count-1);
        }
    }
    private void ascMulTable(final int count){
        if(j>count){
            j=1;
            return;
        }
        if(i!=j){
            i++;
            System.out.print(i+"*"+j+"="+i*j+"\t");
        }else{
            i=0;
            j++;
            System.out.println();
        }
        ascMulTable(count);
    }  
    private int i=0;
    private int j=1;
}
public class Test {
  
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MulTable mul = new MulTable();
        mul.showMulTable(9, MulTable.MulTableEnum.DESC);
        mul.showMulTable(9, MulTable.MulTableEnum.ASC);
    }
  
}
亲,你这题目也不仔细看看,怎么可能对得上要求呢?

Java版递归来了

1
2
3
4
5
6
7
8
9
10
11
12
public void show(int n){
        if (n == 0) {
            return ;
        }else{
            show(--n);
        }
        for(int i = 1; i <= n ; i++){
            System.out.print(i*n + " ");
        }
        System.out.println();
          
    }
唯一的就是用了if语句,唉,楼上的那位兄弟,你那递归和这个相比,是不是有点偏Low了?

某攻城狮的再战作品

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class asdfasf {
  
    public static void main(String[] args) {
        int n = 9;
        int i = 1;
        int line = 1;
        int lastSq = 0;
        while (i <= n * n) {
            System.out.print(i + " ");
            int sq = (int) Math.sqrt(i);
            if (sq * sq == i && sq > lastSq) {
                line++;
                System.out.println();
                i = line;
                lastSq = sq;
            } else {
                i = i + line;
            }
        }
    }
  
}

这个代码可读性稍差一点,当然,里面有if判断,违规了

JavaScript版来了

我们的前端攻城狮也不甘寂寞,冲上来了

1
2
3
4
5
6
7
8
9
10
11
12
13
$(document).ready(function () {
            $("body").html(Print(5));
        });
        var PrintHtml = "";
        function Print(num) {
            var ThisHtml = "";
            for (var i = 1; i <= num; i++) {
                ThisHtml += (i * num).toString() + "&nbsp;&nbsp;";
            }
            PrintHtml = ThisHtml + "<br>" + PrintHtml;
            (num - 1) > 0 ? Print((num - 1)) : PrintHtml;
            return PrintHtml;
        }
嗯嗯,用了?:

某大神的第三次冲刺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class asdfasf {
  
  
 public static void main(String[] args) {
 int n = 9;
 n = n * n;
 int i = 1;
 int line = 1;
 int times = line;
 while (i <= n) {
 System.out.print(i + " ");
  
  
 times = times - 1;
 try {
 System.out.println(1 / times);
 i = i + line;
 } catch (Exception e) {
 line++;
 times = line;
 i = line;
 System.out.println();
 }
  
 }
 }
  
}
这次居然用了反人类的异常来替换IF,确实是让我大大吃了一斤,亲我给归到使用if变体里了。

JavaScript再战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$(document).ready(function () {
            Print(5);
            $("body").html(PrintHtml);
        });
        var PrintHtml = "";
        function Print(num) {
            var ThisHtml = "";
            for (var i = 1; i <= num; i++) {
                ThisHtml += (i * num).toString() + "&nbsp;&nbsp;";
            } PrintHtml = ThisHtml + "<br>" + PrintHtml;
            while ((num - 1) > 0) {
                Print(num - 1);
                num = 0;
            }
        }
嗯嗯,用了两个循环

一个距离成功只有一步之遥的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Test99 {
    public static void main(String[] args) {
        Test99.print(20);
    }
 
    private static void print(int n) {
        for (int i = 1; i <= n; i++) {
            print2(i);
        }
    }
 
    private static void print2(int k) {
        for (int i = 1; i <= k; i++) {
            System.out.print(i * k + " ");
        }
        System.out.println();
    }
}
这个答案,实际上熟悉模式的同学,大致看看就能想出怎么把两个for语句干掉一个的办法,可惜了一点儿。

实践比想法困难的代表

某大神第4次挑战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class MultiplicationTable {
  
    public static void main(String[] args) {
  
        char space = ' ';
        char enter = '\n';
  
        int n = 9;
  
        int i = 1;
        int line = 1;
        int col = 0;
        int current = 1;
        while (i <= (1 + n) * n / 2) {
            System.out.print(current);
  
            // col = col + 1;
            int isZero = ((line - col - 2) >> 31 & 1);
  
            line = line + 1 * isZero;
            col = (col + 1) - (col + 1) * isZero;
            current = line + current + (-current) * isZero;
            System.out.print((char) (space + (enter - space) * isZero));
            i++;
        }
  
    }
  
}
嗯嗯,里面有/有>>有&,总之各种小技巧。偶的答复:

亲,我觉得一个好的算法,首先是简单的,再一个是容易理解的,再一个是有技巧的。 

中间省略N个重复了的代码

C#版的来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
  
typedef void (*pFun)(int m, int k);
  
void f0(int m, int k)
{
    cout<<endl;
}
  
void f1(int m, int k)
{
    pFun fun[2] = {f0, f1};
    cout<<m * k<<" ";
    fun[(k<m)](m, k+1);
}
  
void printLine(int m)
{
    f1(m, 1);
}
  
void run(int m)
{
    int i = 1;
    while (i <= m)
    {
        printLine(i);
        i++;
    }
}
  
int main()
{
    run(9);
    return 0;
}
里面用到了k<m判断语句

SCALA版来了

1
2
3
def mul(n: Long): String = (1L to n).map { i =>
  (1L to i).map(_ * i).mkString(" ")
}.mkString(System.getProperty("line.separator"))
太精练了!!!就是那to了两次是不是两个循环?

非常不错的实现

1
2
3
4
5
6
7
8
9
10
def test99(n):
    i = 1
    j = 1
    while i <= n:
        print '%d ' % (i * j),
        nj = (j % i) + 1
        ni = (j / i) + i
        print '\n' * (ni - i),
        i = ni
        j = nj
唯一就是小小的违规了。

这是啥语言版来着?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package object test {
  def main(args: Array[String]) {
    _99(9)
  }
  
  def _99(m: Int) {
    var i = 1;
    while (i <= m) {
      printLine(i);
      i += 1
    }
  }
  
  def printLine(m: Int) {
    printResult(m, 1);
  }
  
  def printResult(m: Int, k: Int) {
    print(m * k + "\t")
    matchResult(m - k > 0, m, k);
  }
  
  def matchResult(in: Any, m: Int, k: Int) = in match {
    case true => printResult(m, k + 1)
    case _ => println()
  }
  
}
里面有判断语句。

JavaScript版的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
javascript 版, chrome 浏览器, CTRL+SHIFT+I 打开调试器 -> console选项卡 粘贴代码并回车:
  
**/
function _99x(n){
    function iterate(n, callback){
        for(var idx = 1; idx <= n; idx++)
            callback(idx, n);
    }
    iterate(n, function(start, end){
        iterate(start, function(start, end){
            console.log(start * end);
        })
        console.log('-------')
    })
}
原来没有仔细看,以为callback是系统函数,今天仔细看,原来这个是OK的,唯一的问题是换行怎么处理的?

NIM版

1
2
3
4
5
6
7
8
## test.nim
  
for i in 1..9:
    for j in 1..i:
        write stdout, j * i
    write stdout, '\10'
  
## $ nim c -r test.nim
呵呵,标准的就是这么写的。

这个是啥版?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
proc p(n: int) =
    proc walki(j: int, i: int) =
        if j <= i:
            write(stdout, j * i)
            walki(j + 1, i)
        else:
            write(stdout, '\10')
  
    proc walk(i: int) =
        if i <= n:
            walki(1, i)
            walk(i + 1)
    walk(1)
  
p(9)
明显有判断了。

C语言版来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
  
//输出一行
int print_one_row(int i, int n)
{
        return (i <= n) && ((printf("%d ", i*n), print_one_row(i+1, n)));
}
  
//整体输出
int print_all(int n)
{
        return (n && (print_all(n-1), print_one_row(1, n), printf("\n")));
}
  
int main(int argc, char *argv[])
{
        print_all(1); //测试1行
        print_all(9); //测试9行
        print_all(11); //测试11行
        return 0;
}
用了if变体

也不是错的实现

1
2
3
4
5
6
7
8
9
10
11
import sys, math
  
def test99(a):
    for i in xrange((1 + a) * a / 2):
        i = i + 1
        q = int(math.sqrt(i * 2))
        b = q * (q + 1) / 2 - i       
        sys.stdout.write(str(max(q * -b + -b, q * -b + q * q)))           
        sys.stdout.write(chr(10 - max(abs(b), 0) / max(abs(b), 1)))
          
test99(5)
这个性能确实有点差的,sqrt,* / max 好多运算哦

号称邪恶的解法

一个变量是挡不住邪恶的我的, 你是不是要考虑限制内存的使用?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package com.test;
   
   
public class Test99 {
       
    public void print(Integer... oneVar){
        oneVar = new Integer[]{oneVar[0], 1, 1};
        while(oneVar[1]<=oneVar[0]
                && System.out.printf(oneVar[1]*oneVar[2]+"\t")!=null
                &&((oneVar[1] == oneVar[2] && (oneVar[1]++>0 && System.out.printf("\n")!=null) && (oneVar[2]=0)==0) || true)
                ){
            oneVar[2]++;
        }
    }
   
}
简单的说,是把判断隐藏在while里了。

超级技巧版来了

1
2
3
4
5
6
7
function fun(n){
    (n - 1) && fun(n - 1);
    for(var idx = 1; idx <= n; idx++)
        process.stdout.write(idx * n + ' ')
    process.stdout.write('\n')
}
fun(process.argv[2]);
这里的技巧相当高明,隐藏得非常深。

C# 简短版

1
2
3
4
5
6
7
8
9
10
11
12
static int s = 9;
        public static void print(int k=1)
        {
            int m = 1;
            while (m <= k && k <= s)
            {
                Console.Write("{0}*{1}={2}\t", m, k, m * k);
                m++;
            }
            Console.WriteLine();
            if(m<=s) print(m);
        }<span></span>

C#版的,想来想去都要一个if来判断边界啊。

==嗯嗯,如果有一个if,这题就不难了:)

世界上最好的语言PHP版也来了

1
2
3
4
5
6
7
8
9
10
<?php
//生成1-9的数组,我只是快速定义好数组..这不算循环吧。23333
$number = range(1, 9);
//数组递归..
array_walk($number, function($param, $key) {
    for ($i = 1; $i < $key + 2; $i++) {
        echo $param * $i. " ";
    }
    echo '<br/>';
});
range函数是干啥的,里面有没有个循环语句帮你干活?

版本帝的第N版来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class MultiplicationTable3 {
  
    /**
     * 主要是使用了数组初始化后,未赋值的位置为0,来实现复位的效果。<br>
     * cursors数组运行中第一位总是0,变化过程如:<br>
     * {0,0,0,0,0,0,0,0,0}<br>
     * {0,1,0,0,0,0,0,0,0}<br>
     * {0,1,2,0,0,0,0,0,0}<br>
     * {0,1,2,3,0,0,0,0,0}<br>
     *
     * @param n
     */
    public void print(final int n) {
        // 游标控制,多一位,容错
        int[] cursors = new int[n + 1];
        // 基数,系数
        int[] factor = new int[n];
        factor[0] = 1;
  
        // 字符后缀
        char[] suffixChars = new char[n];
        suffixChars[0] = '\n';
  
        int i = 0;
  
        while (factor[0] <= n) {
            int colValue = (cursors[i] + 1);
            System.out.print(colValue * (factor[0]) + " ");
  
            int temp = i;
            i = cursors[i + 1];
            cursors[temp + 1] = cursors[temp] + 1;
            factor[i] = factor[i] + 1;
  
            System.out.print(suffixChars[i]);
  
        }
  
    }
  
    public static void main(String[] args) {
        new MultiplicationTable3().print(9);
    }
  
}

JS版改进型

这里的undefined:部分是不是判断的变体呢?

多线程版来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Test99 {
    private int rowNum;
    private int[] arr;
    private int i;
    public Test99(int rowNum, int[] arr, int i) throws InterruptedException {
        this.rowNum = rowNum;
        //初始化一个长度为N+1的数组,如rowNum=5,数组为[0,0,0,0,0,0]
        this.arr= arr;
        this.i = i;
        try {
            arr[i+1] = arr[i] + 1;
            PrintThread printThread = new PrintThread(arr[++i], rowNum);
            printThread.start();
            new Test99(rowNum, arr, i);
        }
        catch (Exception e) {
            Thread.sleep((arr[--i] + 1) * 100);
            Thread.interrupted();
        }
    }
}
  
class PrintThread extends Thread {
    int length = 0;
    int rowNum = 0;
    public PrintThread (int length, int rowNum) {
        this.length = length;
        this.rowNum =rowNum;
    }
    @Override
    public void run() {
        try {
            Thread.sleep(length * 100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        for (int i = 1; i <= length; i++) {
            System.out.print(i * length + "\t");
        }
        System.out.println();
    }
}
居然有线程,居然有异常,偶的心好凌乱....让偶缕缕

韦达定理版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Test99 {
    public void print(int n) {
        for (int i = 0; i < n * (n + 1) / 2; i++) {
            int row = (int)((Math.sqrt(1 + 8 * i) - 1) / 2);
            int column = i - row * (row + 1) / 2;
            int end = 10 + (int)Math.ceil(1.0 * (row - column) / (row + 1)) * 22;
            System.out.printf("%d%c", (row + 1) * (column + 1), end);
        }
    }
  
    public void printOneline(int n) {
        for (int i = 0; i < n * (n + 1) / 2; i++) {
            System.out.printf("%.0f%c", (Math.floor((Math.sqrt(1 + 8 * i) - 1) / 2) + 1) * (i - Math.floor((Math.sqrt(1 + 8 * i) - 1) /