Foreword
Why do I have to do this tag
以后此标签是C语言学习，会说一些奇淫技巧和算法思路，毕竟逆向搞的就是算(shu)法(xue),再加上本人大一C++学的超级菜，不练习不会啊，正向开发都不会何谈逆向~
Problem and Analysis
Calculate two numbers‘ highest common divisor
我们最先想到的应该是素因数分解法（短除法与之类似）了，将两数进行因数分解，取共同元素组成最大公因数，这是之前我乱写的分解质因数的算法
#include <stdio.h>
int main()
{
int x;
scanf("%d", &x);
for (int y = 2; y <= x; y++)
{
if (x % y == 0)
{
x = x / y;
printf("%d\t", y);
y = 1;
}
}
return 0;
}
这种方法极其简单科学，但是同时也面临着一个很大的问题：时间复杂度，这种暴力计算在计算很大的数上不占优势。我们需进行优化
于是想起之前学过的辗转相除法，我们来进行编程解决，核心如下
while( a > 0 && b > 0 )
{
if( a > b )
a = a % b;
else
b = b % a;
}
虽然觉得这段已经很简单，但是觉得可以再次进行优化（因为感觉”对称度”很高），于是在维基百科上看到了这个
int GCD(int a, int b)
{
if (b)
while((a %= b) && (b %= a));
return a + b;
}
惊为天人，这么优美的算法是怎么想出了来的，三行代码把辗转相除法的思想解释的淋漓尽致，tql
我们来分析一下while((a %= b) && (b %= a))。我们在学习C++的时候知道，while中的赋值语句是先赋值之后会进行判断表达式左侧的值是否为0，同时while中的&&运算符在判断时进行了优化，只要左侧值为0，右侧的语句将不执行。我们直接用27和19进行举例
- a = 27 % 19 = 8 ； b = 19 % 8 = 3
- a = 08 % 03 = 2 ； b = 03 % 2 = 1
- a = 02 % 01 = 0 ； 结束循环(之后的语句不会被执行)
这时候a = 0，b = 1返回a+b的值为1。事实上，值永远是去取a和b经过计算后的最大值，且两个变量的值有某一个必然是0（否则不会退出循环），写入a+b较为简单明了
Link
Problem
print the diamond below
*
***
*****
*******
*****
***
*
原本我想讲这个菱形分成两部分，打印出两个三角形后拼合形成菱形（这也是Ｃ++老师讲的）．但是显然这种方法够粗暴，但是代码量不少，能不能直接打印出来，不”钻空子”?
之后我找了一些代码进行挑选，最终选了一个最奇怪，但我感觉是给我触动最大的．(代码来自知乎大佬WHsT)
#include <stdio.h>
#define ABS(x) ((x) > 0 ? (x) : -(x))
int main()
{
double a = 3, b = 3;
int i, j;
for (i = -a; i <= a; ++i) {
for (j = -b; j <= b; ++j)
putchar((ABS(i)/a + ABS(j)/b > 1) ? ' ' : '*');
putchar('\n');
}
return 0;
}
这段代码简洁精炼，但一开始我没看懂，怎么用double类型？看到define的宏定义我可能明白了，它利用绝对值进行判断，来控制*和 的输出，下面我们具体分析一下这段精密的代码
Analysis
一开始定义的ABS是取绝对值，到主函数中先遍历行，之后是列，关键代码来了putchar((ABS(i)/a + ABS(j)/b > 1) ? ' ' : '*'),这句话的意思直接上代码很难理解，我们上一个表达式
|x|/a+|y|/b<=1
其中a和b是菱形的长和宽的一半，通过这个表达式去判定真正符合条件的点，最终实现打印.从数学层面理解就不难了
Summary
本题不难,但昨天通过这题知道了原来打印图形神马的,其实不一定从结果出发,从问题的本质出发也许会是另一番天地,算法还是要学习啊,什么都不会怎么逆向:)
Impression
Some small tricks
其实在自己编程时我都是尽可能做到最优解,但有一次将自己程序丢到ida用F5大法,在分析的时候发现它竟然把我的算法又进行了优化,遭到狠狠的打脸,很强~~~
下面仅仅利用for循环这个例子给大家细致的看一下,for语句怎么用才能达到较为完美的效果.
Combination
例如:计算100~200内的素数
这个是我之前写的,我们直接上代码
#include <stdio.h>
int main()
{
int j;
for (int i = 101; i <= 200; i++)
{
for (j = 2; j < i / 2; j++)
if (i % j == 0)
break;
if (j == i / 2)
printf("%d\n", i);
}
return 0;
}
在这里,我们没有利用数学层面的优化,仅仅利用代码层面暴力求解,且没有引进math.h头文件的sqrt()函数,只是找遍i/2的因数就停止进而输出
很好看懂的一个程序,我们这时候看第二层循环(第一层仅仅是让数字递增,无法优化),我们观察到for循环中的if语句仅仅是一个break操作,我们知道for循环中间的条件也是控制循环跳出的,那我们就可以将两者写到一个表达式中,进而把算法优化(ida的功劳)为
for ( j = 2; j < i / 2 && i % j; ++j )
;
当然我们利用这个的前提是for语句中仅含if控制程序走向的情况,其他情况还是好好用括号码代码为妙
Simplify
Some easy example
printf
常见的输出:
for (int i = 0; i <= 9; i++)
printf("%d\n", a[i]);
完成从a[0]到a[10]输出
改进后:
for (int i=0; i<10; printf("%d\n", a[i++]));
这给我们提供了一个思路,那就是将尽可能多的要素包含到for语句中,使得代码更加精简与优美,当然这带来一个显著的缺点,比之前的程序不自然,别人读起来会别扭
Infinite loop
很早之前程序员习惯于利用goto来实现无限循环,到现在while(1)和for(;;)早已是大势所趋,主要还是goto语句太过强大,导致程序可读性很低,到后期的维护也会比较难办
Reflection
Present feelings
上周经历了一周（04-22）的数学建模，把我压抑得够呛，现在终于能玩我的计算机了~~十分开心，上周熬了几天，在实验室混了好久。可能是最近习惯了学习新鲜知识，今天的实验课竟然没在划水，一直在搞，今天的算法分析整了个大整数乘法，记录一下好不容易看懂的一个算法。
Analysis
问题如下所描述:
输入两个2^n位大整数X和Y, 用分治法的变形方式实现乘积运算，使时间复杂度降得尽可能低
其实我们应该回忆一下自己在计算乘法时候的采用的算数式，我们其实是把对应位数一样的数字进行相加，而不同的位数要进行相应的进位换算才能在最后进行相加，这不就是分治法吗?
我们以27和41为例：
7与1对应相乘得到最低位，2与1和7与4对应乘积进行相加得到中间位，最后2与4的乘积得到最高位，其中中间位结果位2*1+4*7=30，我们需要把3进位上去，最后的结果为1107
接下来我们把这些进行代码抽象
相关变量：
int len_a = strlen(a); //a为字符串数字，同理，b与之类似
int len_b = strlen(b);
int* num_arr = new int[len_a+len_b];
对应位数：
for (int i=len_a-1; i>=0; --i) {//分别算出各个位数
for (int j=len_b-1; j>=0; --j) {
num_arr[i+j+1] += (b[j]-'0')*(a[i]-'0');//把对应位数的数字直接加起来
}
}
进行进位：
for (int i=len_a+len_b-1; i>=0; --i) {//进位
if (num_arr[i] >= 10) {
num_arr[i-1] += num_arr[i]/10;
num_arr[i] %= 10;
}
}
完成，我们只需将数组num_arr输出即可完成，这其实不算一个创新算法，只是将我们日常使用的方法进行了推广
