浩行天下 ghSky->Blog

最近期末复习正好看到算法的分治策略，里面讲到两种排序算法：合并排序和快速排序。这里大概就谈下自己对算法的理解，代码不是最重要的，思想才是精华，所以这次不打算讲太多代码。

首先说一下分治法的基本思想，分治法是把一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同（这里需要注意分治算法与动态规划的区别）。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这里要谈到的合并排序和快速排序便是分治算法的典型应用之一。

首先看合并排序，其基本思想是将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终讲排好序的子集合合并成为所要求的排好序的集合。算法一般通过计算两个边界的中点作为分界点，然后再递归调用对左半边和右半边分别合并排序，递归中止条件自然是左边界小于右边界，即保证至少有两个元素参与排序。当一轮调用中，左半边和右半边分别排序完成后（或无法再划分进行排序后），就进行合并，其中对元素的真正排序便是在合并中完成的，利用一个临时数组完成对排序后数组两边元素的排序、合并。如下是一个合并排序的过程图，其中S代表mergeSort函数，即递归函数，其中参数待排序数组，左分界点，右分界点；m代表merge函数，即排序、合并函数，其参数分别为待合并数组，目的合并数组，合并左分界点，合并中点，合并右分界点。

再来看看快速排序，其基本思想是对于输入的子数组a[p:r]，按以下3个步骤进行排序：

1. 分解(divide)：以a[p]为某基准元素，将a[p:r]划分成3段，a[p:q-1]， a[q]和a[q+1:r]，使得a[p:q-1]中的任何元素都小于等于a[q]，而a[q+1:r]中的任何元素大于等于a[q]，q在划分中确定；
2. 递归求解(conquer)：通过递归调用快速排序算法，分别对a[p:q-1]和a[q+1:r]进行排序；
3. 合并(merge)：由于对a[p:q-1]和a[q+1:]r的排序在分解过程中就已经完成，所以当前a[p:q-1]和a[q+1:r]中的元素都已经排好序了，无须再执行任何计算，a[p:r]就已经完成排序了。

如下以a = [5, 3, 7, 2, 6, 4, 8, 1, 9]为例，具体分析一下快速排序的过程，【】表示划分元素，｛｝表示需交换元素。

由上述分别对两种算法的说明，大致也能看出两算法的异同之处。两种算法都考虑到使用划分元素的方法进行分治的依据，但合并排序的划分元素是直接去两边界的中点，而快速排序的划分点则是在排序中找到；合并排序首先进行划分，然后再对划分的部分递归调用，而快速排序则是在排序过程中找到划分点，之后再递归调用；再次，合并排序需要借助一个临时数组完成合并操作，而快速排序则不需要特别地合并操作，也无需临时数组，其排序是在划分中完成，而合并则只需简单连接即可。

虽然自己已经对上述算法有了比较具体的了解，但是要深入理解还是需要慢慢体会，领悟其中玄机，同时也需要在不参考参考程序的过程中，完成自己程序的编写，这样不但锻炼了编程能力，更加需要对算法本身有较透彻的理解，所以下一步自己需要用一门语言用自己的方法实现算法。

不同进制之间的转换纯粹是数学上的计算。不过，你不必担心会有么复杂，无非是乘或除的计算。
生活中其实很多地方的计数方法都多少有点不同进制的影子。

比如我们最常用的10进制，其实起源于人有10个指头。如果我们的祖先始终没有摆脱手脚不分的境况，我想我们现在一定是在使用20进制。

至于二进制……没有袜子称为0只袜子，有一只袜子称为1只袜子，但若有两袜子，则我们常说的是：1双袜子。

生活中还有：七进制，比如星期。十二进制，比如“一打”，六十进制，比如分钟……

一、为什么需要八进制和十六进制?

编程中，我们常用的还是10进制……必竟VB是高级语言。
比如：a = 99;
不过，由于数据在计算机中的表示，最终以二进制的形式存在，所以有时候使用二进制，可以更直观地解决问题。但是二进制数太长了。比如int 类型占用4个字节，32位。比如100，用int类型的二进制数表达将是：0000 0000 0000 0000 0110 0100
面对这么长的数进行思考或操作，没有人会喜欢。因此，C,C++ 没有提供在代码直接写二进制数的方法。
　
用16进制或8进制可以解决这个问题。因为，进制越大，数的表达长度也就越短。不过，为什么偏偏是16或8进制，而不其它的，诸如9或20进制呢？

2、8、16，分别是2的1次方，3次方，4次方。这一点使得三种进制之间可以非常直接地互相转换。8进制或16进制缩短了二进制数，但保持了二进制数的表达特点。在下面的关于进制转换的课程中，你可以发现这一点。 阅读全文…

在VF看见的一个题目：
HOHO，占字符……

计算：1/2×3+1/3×4+1/4×5+.....1/99×100

写了个基本程序，不过无法实现分数显示结果

using System;
using System.Collections.Generic;
using System.Text;

namespace Solve_1
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 2;
            int b = 3;
            float ans = 0;
            while (b < = 100)
            {
                float num1 = (float)a;
                float num2 = (float)b;
                ans =ans + 1 / num1 * num2;
                a++;
                b++;
             }
             Console.WriteLine(ans);
        }
    }
}

阅读全文…

第三章的另一个练习
简单的加密

using System;
using System.Collections.Generic;
using System.Text;

namespace Chapter03Exercise394
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("What do you want to do? Encrypt(E) Or Crack(C)");
            string m = Console.ReadLine();
            if (m == "E" || m == "e")
            {
                Console.WriteLine("Please input what you want to encrypt");
                string str1 = Console.ReadLine();
                int count1 = str1.Length;
                for (int i = 0; i < count1; i++)
                {
                    char temp1 = str1[i];
                    int pass = (int)temp1;
                    pass = pass + 5;
                    char temp2 = (char)pass;
                    Console.Write(temp2);
                }
                Console.ReadLine();
            }

            else if (m == "C" || m == "c")
            {
                Console.WriteLine("Please input what you want to crack");
                string str2 = Console.ReadLine();
                int count2 = str2.Length;
                for (int i = 0; i < count2; i++)
                {
                    char temp1 = str2[i];
                    int pass = (int)temp1;
                    pass = pass - 5;
                    char temp2 = (char)pass;
                    Console.Write(temp2);
                }
                Console.ReadLine();
            }
            else
            {
                Console.WriteLine("Input Error!!!");
                Console.ReadLine();
            }
        }
    }
}

练习，自己研究的
希望DX多多指点！

using System;
using System.Collections.Generic;
using System.Text;

namespace Chapter03Exercise393
{
    class Exercise3_9_3
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Please Input:");
            String str = Console.ReadLine();
            String str2 = str;
            String[] str1 = str.Split(new char[] { '+', '-', '*', '/' });
            string temp = str1[0];
            char mark = Convert.ToChar(str[temp.Length]);
            double ans = 0;
            double num1 = Convert.ToDouble(str1[0]);
            double num2 = Convert.ToDouble(str1[1]);
            switch (mark)
            {
                case '+': ans = num1 + num2;
                    break;
                case '-': ans = num1 - num2;
                    break;
                case '*': ans = num1 * num2;
                    break;
                case '/': ans = num1 / num2;
                    break;
                default: ans = 0;
                    break;
            }
            Console.WriteLine(str2 + "=" + ans);
            Console.ReadLine();
        }
    }
}