3

这是为了下学期即将到来的学校额外学分分配。我必须在屏幕上打印一个段落,但字符数是代码必须小于段落中的字符数。该段如下:

“我保证,每一个带有我名字的程序都应该由我(以及我的合著者,如果有的话)编写,并且我完全理解这个程序。我提交的每个程序都应该完全是我自己的作品,除非另有说明。我明白学术不诚实不仅包括抄袭他人的作品,还包括教唆或协助抄袭。与过去或现在提交的任何其他提交的代码相似,无论解释如何,都不会获得任何荣誉。我理解学术不诚实的后果是 ' F' for the class。我承诺通过编写自己的程序来学习Java。我将努力关注细节并编写我自己和其他程序员都可以理解的程序。

程序中的字符总数应少于承诺中的字符总数(可打印 655 个,总共 793 个)。

该程序可以不接受任何输入......没有文件,下载等。

我最初的想法是,既然没有人能够做到,那肯定超出了我们目前在课堂上所学的范围。由于它必须更少,因此您显然不能只逐行打印段落,这是每个人在作业的第一部分(常规学分)中所做的。

我已经使用 java.util.zip 研究了字符串压缩,但我一直遇到不允许输入的问题。我现在搁置的一个想法是:有没有办法以压缩形式对字符串进行编码,使代码比段落的未压缩版本更少字符,并且在我将字符串打印到控制台时简单地解压缩字符串?

我也涉足 ASCII 值,但是,ASCII 值仅代表字符,并且所有 ASCII 值的字符长度都比它们用来表示的字符长,所以我没有看到它的用途。

我现在确定的想法是获取最长的重复单词并为它们分配一个字符串变量名称。然后,只需用可变连接样式替换段落中的单词。到目前为止,这是我的代码:

import static java.lang.System.out;

public class Pledge {
  public static void main(String[] args){
    String s=" understand ",p=" program",z=" academic dishonesty ",c=" copying",i="I pledge ";
    out.println(i+"that every"+p+" with my name on it shall be written by me (and my co-authors, if any) and that i fully"+s+"the"+p+". Every"+p+" I submit shall be entirely my own work unless otherwise attributed. I"+s+"that"+z+"not only includes"+c+" other people's work, but also abetting or facilitating"+c+". Code that is similar to any other submission past");
    out.println("or present will get no credit whatever the explanation. I"+s+"that the consequence of"+z+"is a grade of 'F' for the class."+i+"to devote my efforts to learning Java by writing my own"+p+"s. I shall strive to be attentive to detail and write"+p+"s "+s+"able by myself and other"+p+"mers.");
  }
}

随附的代码是 762 个可打印字符。因为我少了 112 个字符,而且代码已经看起来很糟糕,有两个巨大的 println 语句,我有点觉得我没有走在正确的轨道上。我不希望为我编写任何代码(我讨厌那样),但非常感谢一些提示或技巧将我推向正确的方向。谢谢!

4

3 回答 3

2

您可能想要研究的一件事是Huffman encoding。该方法类似于您发布的程序中的方法,但在压缩段落方面更加彻底。因此,您可以(预先)压缩文本,将压缩版本放在源文件中,解压缩并打印。

还有一些小技巧也可以刮掉一些字符;例如,

  • main(String[] args)可以main(String[]v)(保存 4 个字符)
  • 您可以使用比 更短的名称Pledge,可能是单字符名称(保存 5 个字符)
  • 您可以将所有内容放在一行上(保存了许多字符)

它们是小东西,但它们会加起来。

于 2012-11-21T21:13:32.023 回答
1

一个创造性的解决方案可能是用 Unicode 编写程序并使用 UTF-16 对字符串进行编码。这允许您使用一半的“可打印字符”来存储字符串。例如:

public static void main(String[] args) throws Exception {
    String s = "䤠灬敤来⁴桡琠敶敲礠灲潧牡洠";
    System.out.println(new String(s.getBytes("UTF-16BE"),"UTF-8"));
}

打印I pledge that every program。输出为 28 个字符,但用于存储字符串的“可打印字符”数仅为 14。要编码 793 个可打印字符,字符串需要 397 个字符,而实际代码则需要 258 个字符.

于 2012-11-21T21:45:50.940 回答
0

您当前方法的改进是使用printf()及其显式参数索引功能。这将为原始字符串中的每次出现节省 1 个字符(从而让您“压缩”较短的子字符串。它还摆脱了字符串变量声明,即每个子字符串少三个字符和一点。

剧透的 ideone 版本在这里:http://ideone.com/lnrTrG -我设法把它减少到 784 个字符,而无需使用任何非常聪明的东西。我对提取的子字符串的选择也可能不是最优的。

我尝试使用 实现相同的功能MessageFormat.format(),但它不会替换所有占位符。考虑到版本有多接近限制printf(),压缩较短子字符串的能力(因为MessageFormat's 的显式索引占位符比printf()'s 短一个字符)甚至不会抵消额外的 32 个字符的开销java.text.MessageFormat.format()。(也就是说,这可能值得一试。您仅在占位符上保存了 29 个字符,所以它很接近。)


您的问题中的另一点也有直接答案:

有没有办法以压缩形式对字符串进行编码,使代码比段落的未压缩版本更少字符,并且在我将字符串打印到控制台时简单地解压缩字符串?

您已经发现java.util.zip,缺失的部分是base-64 编码。这将允许您将压缩字节存储在由可打印字符组成的字符串中。它将占用比编码数组的长度更多的字符,但(幸运的是)远少于原始字符串。(它也应该比直接写出字节数组值更短。)您可以使用实用程序方法DatatypeConverter来处理这种编码。(感谢@owlstead 的提示。)

我的同事提出的一种比 base-64 更好的更好方法是简单地使用像 Latin-1 这样的传统字符集对压缩数据进行编码。由于大多数 Latin-1 字符都是可打印的,因此可以使用一个字符将它们写入 Java 字符串文字。需要转义的少数仍然会比 base-64 少。如果您的源文件也可以用 Latin-1 编码,这也将避免争论字符和字节之间的区别。

于 2012-11-22T02:19:14.330 回答