`

教孩子学编程: 幻方及其编程求解

阅读更多

 

旨在培养孩子们对编程,科学的兴趣.

 

幻方(Magic Square)是一种将数字安排在正方形格子中,使每行、列和对角线上的数字和都相等的方法。

 

算法介绍:

Magic_square@ EN Wikipedia

Magic_square@ 中文 Wikipedia

幻方@百度百科

 

相似的问题供编程学习.

Problem 166 Criss Cross @Euler

 

Ruby编程实现

Magic Squares (#124) @rubyquiz

 

上面的链接有一个Download Solutions链接. 我下载了一份David Tran的ruby代码放到这里. 一百来行代码, 涵盖了三种情况.

#---------------------------------------------------------------#
#                                                               #
#  Program   : Magic Square                                     #
#  Author    : David Tran                                       #
#  Date      : 2007-05-20                                       #
#  Blog      : http://davidtran.doublegifts.com/blog/?p=27      #
#  Reference : http://mathworld.wolfram.com/MagicSquare.html    #
#                                                               #
#---------------------------------------------------------------#
class MagicSquare

  def initialize(size = 3)
    raise "Error: size must greater than 2." if size < 3
    @magic_square = if (size % 2 != 0)
                      OddMagicSquare.new(size)
                    elsif (size % 4 == 0)
                      DoublyEvenMagicSquare.new(size)
                    else
                      SinglyEvenMagicSquare.new(size)
                    end
  end

  def size
    @magic_square.size
  end

  def [](i,j)
    @magic_square[i,j]
  end

  def to_s
    digits = (size * size).to_s.size
    divider = '+' + '-' * ((digits + 2) * size + (size - 1)) + "+\n"
    (0...size).inject(divider) do |s, i|
      (0...size).inject(s + "|") do |s, j|
        s + " #{self[i,j].to_s.rjust(digits)} |"
      end + "\n" + divider
    end
  end

  def is_magic_square?
    size = self.size
    n = size * size

    array = Array.new(n)
    (0...size).each do |i|
      (0...size).each do |j|
        index = self[i,j] - 1
        return false if (index < 0) || (index >= n) || array[index]
        array[index] = true
      end
    end
    return false unless array.all?

    sum = size * (size * size + 1) / 2
    (0...size).each do |i|
      return false if sum != (0...size).inject(0) { |s,j| s + self[i,j] }
      return false if sum != (0...size).inject(0) { |s,j| s + self[j,i] }
    end
    return false if sum != (0...size).inject(0) { |s,i| s + self[i,i] }
    return false if sum != (0...size).inject(0) { |s,i| s + self[i, size-1-i] }
    true
  end

  private
  #------------------------------------------------------------------#
  class OddMagicSquare
    attr_reader :size

    def initialize(size)
      @size = size
      n = @size * @size
      @array = Array.new(n)
      i, j = 0, @size/2
      (1..n).each do |v|
        @array[get_index(i,j)] = v
        a, b = i-1, j+1
        i, j = self[a,b] ? [i+1, j] : [a, b]
      end
    end

    def [](i, j)
      @array[get_index(i,j)]
    end

    private
    def get_index(i, j)
      (i % @size) * @size + (j % @size)
    end
  end
  #------------------------------------------------------------------#
  class DoublyEvenMagicSquare
    attr_reader :size

    def initialize(size)
      @size = size
    end

    def [](i, j)
      i, j = i % @size, j % @size
      value = (i * @size) + j + 1
      i, j = i % 4, j % 4
      ((i == j) || (i + j == 3)) ? (@size*@size+1-value) : value
    end
  end
  #------------------------------------------------------------------#
  class SinglyEvenMagicSquare
    attr_reader :size

    L = [4, 1, 2, 3]
    U = [1, 4, 2, 3]
    X = [1, 4, 3, 2]

    def initialize(size)
      @size = size
      @odd_magic_square = MagicSquare.new(@size/2)
    end

    def [](i, j)
      i, j = i % @size, j % @size
      ii, jj = i / 2, j / 2
      center = @size / 2 / 2
      value = @odd_magic_square[ii, jj]
      case
        when ii < center then L
        when ii == center then (jj == center) ? U : L
        when ii == center+1 then (jj == center) ? L : U
        else X
      end [i%2*2 + j%2] + 4 * (value - 1)
    end
  end
  #------------------------------------------------------------------#
end

if __FILE__ == $0
  #puts MagicSquare.new(ARGV[0].to_i)
  puts MagicSquare.new(5)
end

 

其他的一些讨论.

http://codegolf.stackexchange.com/questions/12430/generate-a-grid-of-sums

 

 

 

 

 

 

分享到:
评论

相关推荐

    Matlab高效编程25个案例分析

    MATLAB快速入门、重新认识矢量(向量)化编程、MATLAB处理海量数据、匿名函数类型介绍、嵌套函数类型介绍、积分以及积分方程求解案例、优化及非线性方程(组)求解案例、人脸图像压缩与重建案例、有关预测分类的案例...

    算法与分析实验五:分枝限界法

    【实验目的】 应用分枝限界法的算法设计思想求解单源最短路径问题。...采用分支限界法编程求源点0到终点6的最短路径及其路径长度。 要求完成:⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析

    Linux多线程服务端编程:使用muduo C++网络库

    《Linux多线程服务端编程:使用muduo C++网络库》主要讲述采用现代C++在x86-64 Linux上编写多线程TCP网络服务程序的主流常规技术,重点讲解一种适应性较强的多线程服务器的编程模型,即one loop per thread。...

    分布式约束优化问题及其求解算法.pdf

    #资源达人分享计划#

    西南交通大学,回溯法,小孩搭积木,一个小孩手中有N块正方形的积木,他总是想不同的方法来搭建各种不同的楼梯。

    1. 理解回溯法的求解过程。 2. 分析回溯法的时间复杂度,比较回溯法算法与其他算法的时间效率差异。 3. 学会如何利用回溯法求解具体问题,了解动回溯法的应用范围及在实际应用中的局限性 1. 写出采用回溯法求解.上述...

    基于高斯伪谱法的二阶常微分方程求解(Matlab实现)

    适用人群:适用于对高斯伪谱法及其在常微分方程求解方面有一定了解的学者和工程师,具备一定 Matlab 编程能力和数值计算基础。 使用场景和目标:该代码可用于求解二阶常微分方程及其相关问题,如优化问题、最优控制...

    matlab求解一维波动方程.rar

    matlab求解一维波动方程

    matlab的高效编程技巧与应用(25个案具体例分析)

    第1章matlan快速入门第2章重新认识向量化编程第3章MATLAB处理海量数据第4章匿名函数类型第5章嵌套函数类型第6章积分以及积分方程案例第7章MATLAB优化及非线性方程(组)求解案例第8章案例15:人脸图像压缩与重建第9...

    面向对象编程方法

    4.1一个简单的程序 4.2 类和对象 4.3 类的继承、重载与多态 4.4 运算符的重载 4.5 接口及其实现 4.6 方法的委托 4.7 常用的几个类 4.8 命名空间

    [并行计算——结构·算法·编程].陈国良.文字版

    本书以并行计算为主题,主要讨论并行计算的硬件基础——当代并行计算机系统及其结构模型,并行计算的核心内容——并行算法设计与并行数值算法以及并行计算的软件支持——并行程序的设计原理与方法。本书强调融并行机...

    大学数学建模培训资料 MATLAB及其应用 MATLAB基础入门教程含代码及绘图 第1章 基础准备及入门 共33页.pdf

    不希望学生在编程上化太多时间,课程目的不是学习编程。 紧密结合科学的前沿。 论文=Matlab+word。 MATLAB的特点: 编写程序犹如在演算纸上排列出公式与求解问题。 语法非常简单,编程效率高,易学易懂,...

    C语言实现迷宫问题求解

    使用“穷举求解”方法实现迷宫问题求解,以递归形式的算法求得迷宫中所有可能的通路,以方阵形式输出迷宫及其通路。

    并行计算:结构算法编程(修订版)

    《并行计算:结构算法编程(修订版)》以并行计算为主题,主要讨论并行计算的硬件基础——当代并行计算机系统及其结构模型,并行计算的核心内容——并行算法设计与并行数值算法以及并行计算的软件支持——并行程序的...

    MATLAB语言高级编程

    主要介绍了MATLAB的编程基础,包括MATLAB的变量、MATLAB的运算符、矩阵的创建及运算等;MATLAB的数值与符号功能,包括多项式分析、符号对象创建与分析;高级语言的科学计算功能,包括插值、拟合及方程的求解等;...

    VC与Labview、Matlab编程论文资料[2].rar

    基于ActiveX引擎的VC_与Matlab混合编程及其应用.pdf 基于ARM7和VC平台的高分辨率红外触摸屏设计.pdf 基于AT89C52与MFC的电阻率分布监测系统.pdf 基于COM_VC_Word技术的产品设计说明书自动化研究.pdf 基于COM组件的...

    动态规划法、贪心算法、回溯法、分支限界法解决0-1背包

    1) 动态规划法求解问题的一般思路,动态规划法求解本问题的思路及其C/C++程序实现与算法的效率分析。 2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现...

    数学建模编程培训

    提供数学建模编程指导的电子书籍 目录: 目 录 1 Matlab 软件 ........................................................................................................... 1 1.1 基本介绍.......................

    「数学建模MATLAB必备程序源代码」微积分和微分方程源代码

    能学到什么:①数值积分、微分方程求解等算法如何在 Matlab 中实现;②符号计算、变量定义、函数调用等语言特性在 Matlab 中的应用;③Matlab 中常用库函数的使用方法及其内部实现原理。 阅读建议:此资源以开发简化...

    论文研究-基因表达式编程的LFC方法及其应用.pdf

    介绍了基因表达式编程的基本原理,提出了具有线性复杂度的个体适应度评估方法(LFC),并且在遗传操作中采用自适应代沟替代策略,解决了标准GEP算法在求解复杂问题时时空效率低的问题。仿真表明,与标准GEP算法相比...

    2006 王文波 数学建模及其基础知识详解

    数学建模及其基础知识详解 作者:王文波 出版社:武汉大学出版社 出版日期:2006年5月 版次:1 本书详细、系统地介绍了数学建模中所用到的微积分、线性代数、常微分方程、概率论与数理统计、最优化和图论等知识...

Global site tag (gtag.js) - Google Analytics