本系列博客为个人刷题思路分享，有需要借鉴即可。
今天是收集了近期遇到了几道带有鲜明的数学性质的编程题，特地整理了一下进行分享
1.题目链接：
T1:LINK
T2:LINK
2.详解思路：
T1:
思路1：
总感觉上面写的解析也能读，就是没有图不是很完善，这里就补充一下解析吧。
思路2：暴力求解，一个一个试。分析略。
下面是思路1代码示例：
#include <stdio.h> int main() { int m; while(~scanf("%d", &m)){ int start = m * (m - 1) + 1;//找到对应m^3的起始奇数 char buf[10240] = {0}; //sprintf(buf, format, ...) 与printf用法类似，格式化字符串但是不用于打印而是放到一个buf中 sprintf(buf, "%d", start);//先将起始奇数转换成为字符串存入buf中 for (int i = 1; i < m; i++) { //然后将紧随随后的m-1个奇数数字转换为字符串，按照指定格式放入buf中 //%s+%d, 要求先有一个字符串，然后是+符号，然后是个数字的格式，对应是buf原先的数据，和奇数 sprintf(buf, "%s+%d", buf, start+=2); } printf("%s\n", buf); } return 0; }
下面是思路2的代码示例：
#include <stdio.h> int main() { int n; //搞个空间 while (scanf("%d", &n) != EOF) { int a = 0;//这是可能滴起点 int sum = 0; int i = 0; int j = 0; //试一下，找到起点 for (i = 73; i <= n * n * n; i += 2) { sum = 0; int t = i; for (j = 0; j < n; j++) { a = t; sum += t; t += 2; } if (sum == (n * n * n)) { break; } } //a是最后一个值，回归最初一个值 a = a - (n - 1) * 2; //输出 printf("%d", a); for (i = 0; i < n - 1; i++) { printf("+%d", a += 2); } } return 0; }
T2：
这里之前看到一篇比较好的文章解析过这个题目，我这里就直接把链接放过来了。
https://blog.csdn.net/wyd_333/article/details/126640830
下面是代码示例：
#include <stdio.h> int main() { long n, k; //本题中数值比较大，应用long来定义整数 while(~scanf("%ld %ld", &n, &k)) { if (k == 0) //单独判断k==0的情况 { printf("%ld\n", n * n); //任意数对的取模结果都是大于等于0的 continue; } long count = 0; for(long y = k + 1; y <= n; y++) //y的范围：k+1到n { //每种情况都加起来 count += ((n / y) * (y - k)) + ((n % y < k) ? 0 : (n % y - k + 1)); } printf("%ld\n", count); } return 0; }
T3:圆环结构
这两道题是一起的，比较有意思
先说思路：双指针法，一个快一个慢，如果快的可以追得上慢的，就是圆环，追不上就不是。
第一题的思路比较简单，第二题的话一个思路是推导数学公式，发现玄机，另一个方法就是把第二题当成两个链表找交点的那个题来做链接：LINK（仅作思路分享，下面不说明）。
那怎么设置走几步呢？slow一次走一步，fast一次走两步？slow一次走一步，fast一次走三步？
先说结论：slow与fast如果一次走的差值为1，那么如果是环形结构百分之一百可以追上。如果slow与fast走的差值为2，也可以追上。（有部分博客说差值为2是不能追上的，其实再推导一下，就可以发现是可以追上的）。
下面是一些证明图片：
由上可得：如果slow与fast步差为1，且为环形结构，一定可以追上。
由上可知：如果一个指针从链表头走，一个从相遇点走，两者必定再圆环的起始处相遇，这个条件是解第二道题的关键
由上可知：slow走一步fast走三步的情况下，通过简单的推理发现可能会存在追不上的情况，但这个推理是满足N为奇数且C-1为奇数的条件下，但是如果我们以“当slow走到圆环口”时候两者的路程是两倍的关系列式子，就发现这个推论是错误的，因为两个条件不能同时满足，证明如下：
综上，slow与fast如果一次走的差值为1，那么如果是环形结构百分之一百可以追上。如果slow与fast走的差值为2，也可以追上。（有部分博客说差值为2是不能追上的，其实再推导一下，就可以发现是可以追上的）。
下面分别是两道题的解答：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while(fast&&fast->next) { slow=slow->next; fast = fast->next->next; if(fast == slow) { return true; } } return false; }
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while(fast&&fast->next) { slow=slow->next; fast = fast->next->next; if(fast == slow) { struct ListNode * meet = slow; struct ListNode * headx = head; while(meet!=headx) { meet = meet->next; headx = headx->next; } return meet; } } return NULL; }
完。
