-
POJ 2748 推公式循环问题
2012-11-20 11:58:30话说这题TLE了n次,我就知道是输入输出问题,刚开始真心相当无奈(套用大牛代码也TLE),后来突然想起来改用C++提交,怒AC。。。(看来大牛平常也用C++提交啊!g++就是一个坑爹编译器.....) 公式推出来很简单,根据...话说这题TLE了n次,我就知道是输入输出问题,刚开始真心相当无奈(套用大牛代码也TLE),后来突然想起来改用C++提交,怒AC。。。(看来大牛平常也用C++提交啊!g++就是一个坑爹编译器.....)
公式推出来很简单,根据题意,F(n)=F(n-1)+2F(n-2)+...+nF(1)+1,试了几组测试数据发现F(n)和兔子数列有关,F(N)是兔子数列的第n-1项,有此得F(n)=3F(n-1)-F(n-2),后来通过最初的公式推导出了这个。。。果断用矩阵快速幂推,发现超时,这是突然看到数据量很大,果断想到了斐波那契模一个数的循环问题。。现在就这个问题证明一下:若斐波那契数列模一个数存在循环节,则循环节必从1开始,且循环最后的两个数必是1和0。。。证明用反证法:若循环节不在第一位,设F(x)=f(y),f(x+1)=f(y+1),则可以证明F(x-1)=f(y-1),与之前假设F(x-1)!=f(y-1)不符合,所以循环一定在第一个,也就推出循环后两个数是1和0。。。初始化的时候,用F(n)=3f(n-1)-f(n-2)初始化,循环节折半为75000,代码略
-
sql server在表字段里面循环运行公式(运用在计算电商产品规格数量等问题)
2020-07-20 22:15:47--1、生成对应字段的计算公式 drop table ##T1 ;with x1 as ( select row_number()over(order by id) ids,id,'select @t='+replace(replace(replace(replace(cc,'ml',''),'g',''),'x','*'),'×','*') sql from ( ...以上图为例,提取规格内容为500x3+200存储在数据库表里,当产品数量级大时,可以循环运行下面代码计算规格总数,便于求规格均价的分析场景。
使用SP_EXECUTESQL方法
--1、生成对应字段的计算公式 drop table ##T1 ;with x1 as ( select row_number()over(order by id) ids,id,'select @t='+replace(replace(replace(replace(cc,'ml',''),'g',''),'x','*'),'×','*') sql from ( select id,title,replace(bb,substring(ctool.dbo.GetRegexMatchGroups(bb,'([\u4e00-\u9fa5]+)',0,100),1,100),'')cc from ( select *,replace(aa,substring(ctool.dbo.GetRegexMatchGroups(aa,'([\u4e00-\u9fa5]+)',0,100),1,100),'') bb from test.dbo.vivian_guige_temp ) b ) c where cc not like '%[0-9][lk]%' ) select * into ##T1 from x1 select * from ##T1 --ids便于做循环判断,id是原始数据的唯一标志,便于匹配回原结果表 --2、生成临时表存放循环计算的字段结果 drop table ##T2 create table ##T2(id int,specs int) declare @id int declare @a nvarchar(100) declare @name int declare @i int declare @j int set @j=1 select @i=max(ids) from ##T1 while @j<=@i --循环条件,确定需要循环的次数 begin select @id=id,@a=sql from ##T1 where ids=@j EXEC SP_EXECUTESQL @a, N'@t int output', @name OUTPUT; insert into ##T2 values(@id,@name) set @j=@j+1 end
运行结果:
1、运行临时表##T1查询的结果
2、循环计算后存储在临时表##T2的结果
备注:可以上网详细了解SP_EXECUTESQL的用法,博主也是试了很多种方式才求出来结果,如果有更好的方法实现可以评论告知一下,感激~
-
约瑟夫问题(循环链表法和公式法)python版
2019-08-13 16:42:16约瑟夫问题 N个人站在一个等待被处决的圈子里。第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个人就是最后的胜利者。 问题描述 输入:n,m。其中n为总人数,依次编号为0,1…n...约瑟夫问题
N个人站在一个等待被处决的圈子里。第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个人就是最后的胜利者。
问题描述
输入:n,m。其中n为总人数,依次编号为0,1…n,m为被处决的报数数值。
输出:最后活下来人的编号。解决方案
1.循环单链表法
用循环单链表去模拟这个过程。n个人看做n个链表节点,节点1的value为1,节点1的next指向节点2,节点2的value为2,节点2的next指向节点3,…,节点n的value为n,节点n的next指向节点1,构成一个循环单链表。然后从节点1开始报数,如果报数到m就被删除,最后剩下的那个节点的value就是活下来人的编号。python代码如下:
class Node: def __init__(self, value): self.value = value self.next = None def create_linkList(n): head = Node(1) pre = head for i in range(2, n+1): newNode = Node(i) pre.next= newNode pre = newNode pre.next = head return head n = 8 # 总的个数 m = 3 # 数的数目 if m == 1: # 如果被处决的报数为1,直接输出最后一个值 print(n) else: head = create_linkList(n) pre = None cur = head while cur.next != cur: # 终止条件是节点的下一个节点指向本身 for i in range(m-1): pre = cur cur = cur.next pre.next = cur.next cur.next = None cur = pre.next print(cur.value)
2.公式法
递推公式:
代码如下:n = 8 # 总的个数 m = 3 # 数的数目 if m == 1: # 如果被处决的报数为1,直接输出最后一个值 print(n) else: i = 0 a = list(range(n)) while len(a) > 1: i =(i+2)%len(a) del a[i] print(a[0] + 1)
参考:
-
数列递推公式的实现,采用C语言的运用循环的方式,如何实现这个问题的解决?
2019-02-14 01:27:04Problem Description Mr. Pote's shop sells beans now. He has N bags of beans in his warehouse, and he has numbered them with 1, 2, …, N according to their expired dates. The i-th bag contains Wi ... -
指数循环节问题
2018-07-28 21:06:26指数循环节问题:需要对指数进行降幂处理才能计算 比如:ans = 2 ^ n % mod 其中1 <= n <= 10^100000和1 <= m <= 10^6 这里由于n很大,所以需要进行降幂。那么实际上有如下降幂公式...指数循环节问题:需要对指数进行降幂处理才能计算
比如:ans = 2 ^ n % mod
其中1 <= n <= 10^100000和1 <= m <= 10^6这里由于n很大,所以需要进行降幂。那么实际上有如下降幂公式
A^B mod C = A ^ (B % phi(C) + phi(C)) mod C;
有了上述公式,很多题目就可以迎刃而解了。
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N=1000005; typedef long long LL; char str[N]; int phi(int n) { int rea = n; for(int i=2; i*i<=n; i++) { if(n % i == 0) { rea = rea - rea / i; while(n % i == 0) n /= i; } } if(n > 1) rea = rea - rea / n; return rea; } LL multi(LL a,LL b,LL m) { LL ans = 0; a %= m; while(b) { if(b & 1) { ans = (ans + a) % m; b--; } b >>= 1; a = (a + a) % m; } return ans; } LL quick_mod(LL a,LL b,LL m) { LL ans = 1; a %= m; while(b) { if(b & 1) { ans = multi(ans,a,m); b--; } b >>= 1; a = multi(a,a,m); } return ans; } void Solve(LL a,char str[],LL c) { LL len = strlen(str); LL ans = 0; LL p = phi(c); if(len <= 15) { for(int i=0; i<len; i++) ans = ans * 10 + str[i] - '0'; } else { for(int i=0; i<len; i++) { ans = ans * 10 + str[i] - '0'; ans %= p; } ans += p; } printf("%I64d\n",quick_mod(a,ans,c)); } int main() { LL a,c; while(~scanf("%I64d%s%I64d",&a,str,&c)) Solve(a,str,c); return 0; }
-
约瑟夫环实现(循环链表和数学公式法)
2020-03-22 19:42:33约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。 人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕... -
鸡和兔子同笼的问题两种解决方案 1,传统公式求解 2.利用循环语句求解
2017-07-21 16:34:00//设变量鸡兔的数量分别为x,y 则会有x+y=a 2x+4y=b >(化简公式得到下面的函数) y = (b - 2 * a) / 2;//兔子的数量与总头数和总脚数之间的函数关系 System.out.println("兔的个数:" + y); System.out.... -
scanner 死循环问题
2015-09-21 20:39:06欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来,用它写博客...LaTex数学公式 UML序列图和流程图 离线写博客 导入导出Markdown文件 丰富的快捷键 快捷键 加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl -
easypoi导出模板Excel公式无效问题解决
2020-06-16 17:33:14今天在使用easypoi的导出模板Excel的时候,带有公式的单元格会失效,是一个字符串或者覆盖的情况(覆盖主要是因为我循环生成行数据会替换公式的那个单元格)。 通过寻找到那个采用公式的单元格,在excel赋值之后再拿... -
HDU-找循环节-给定递推公式计算取模
2015-01-27 21:33:18问题及代码: /* *Copyright (c)2014,烟台大学计算机与控制工程学院 *All rights reserved. *文件名称:HDU.cpp *作 者:单昕昕 *完成日期:2015年1月27日 *版 本 号:v1.0 *问题描述:Time Limit : 2000/... -
C语言 数组循环左移问题
2017-09-01 15:19:05如有元素个数为n的序列: abcdefgh 要求循环左移 p位(如设置p=3),则要求操作后的序列从 abcdefgh 变为: defghabc 把 abc 设为序列A,defgh设为序列B 先将 A 逆置得到 cba 再将 B 逆置得到 hgfed 得到 cbahgfed... -
约瑟夫环问题(链表 + 公式)
2021-01-10 11:20:40约瑟夫环 ...而我们的问题是求出最后一个自杀的人 解决约瑟夫环问题方法 一、单向循环链表 我们很容易想到的是用数据结构中的单向循环链表,构成逻辑上第一个环,假设有n个人,那么就需要定义n个结点。 -
电枢公式
2020-10-19 23:54:42电枢公式讨论的是循环等步转圈问题。循环等步就是线性绕法,这种绕法最常用也最简单。电枢公式主要讨论的就是线性绕法下的 同绕关系, 阶, 可达 以及一些同绕恒等式,至于非线性绕法会使问题变得复杂与难以处理,分析... -
递归与循环的效率问题
2016-02-19 19:38:34递归与循环的效率问题 一摆案例: Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。(0) 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。 要求:1s内,256M内 考点:1简单循环... -
leetcode之约瑟夫环问题,妙哉公式法
2020-03-30 11:42:49约瑟夫环问题 约瑟夫环问题是N个人围成一圈,从第一个人开始报数...在我们学习基础的数据结构时,循环链表可谓是专为约瑟夫环问题而生,其实这是该问题的暴力法版本,我们用一个循环链表存储题目中的N个人,然后开始... -
Hdu 4335 What is N? 欧拉函数降幂公式 + 循环节
2016-08-28 16:16:52a^n mod c= a^(n mod phi(c) + phi(c)) mod c (n >= phi(c) ) n! mod phi(c) = 0 n!的因子只需包含 phi(c) 因为... mod phi(c) 都等于0 最后问题转化成有多少个nmod p = b; (a + b)^n = (a mod p + b mod p) ^ n (m -
【杭电oj】1799-循环多少次?(递推公式 && 思路)
2018-06-04 22:02:10思路:此题需要一点转换的思维,题目中有m个循环,并且我们可以发现后面的循环中的指针一定比前面一个大,并且会出现从n个数中取m个数的所有可能性(前面的数比后面小就行,比如1,3,4),那么问题可以转换为从n个数... -
有限域中的循环矩阵在密码学方面的相关问题
2021-02-21 03:14:19利用有限域上循环矩阵的性质,使用2种不同方法去解决有限域上可逆循环矩阵的个数问题.最后给出有限域上可逆循环矩阵个数的计算公式,并对多变量密码学中的循环矩阵的应用进行简要分析,这对矩阵理论研究和相关密码学的... -
链队列约瑟夫环c++代码_047题-[编程入门||数据结构入门]报数问题-...循环链表/队列标准,公式推导On实现...
2020-12-19 12:04:49首先,该问题就是典型的约瑟夫环问题# 什么是约瑟夫环问题?约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的... -
10.2.7使用排列组合使用递推公式计算其值(递归将大问题化解成小问题)
2020-01-10 16:45:20递归计算排列组合的值 ... * 其实也可以直接用公式计算 循环结构(先分别算出分子个分母) * */ #include <stdio.h> extern int combin(int x, int y); void main() { int m, n, result; printf... -
超详细的长短时记忆LSTM和门控循环单元GRU的反向传播公式推导!
2018-05-08 20:42:42门控循环单元GRU 好文章(有助理解):https://zhuanlan.zhihu.com/p/28297161 长短时记忆LSTM LSTM模型是用来解决simpleRNN对于长时期依赖问题(LongTerm Dependency)... -
指数循环节问题学习&&补题
2018-07-31 16:26:38今天来学习一个新的东西---指数循环节。在有些题目中我们需要对指数进行降幂处理才能计算。比如计算 其中和 这里由于很大,所以需要进行降幂。那么实际上有如下降幂公式 有了上述... -
循环队列的容量大小计算问题疑惑
2020-08-26 20:27:11循环队列牺牲一个单元来区分队空和队满,入队时少用一个队列单元 队中元素个数:(Q.rear+MaxSize-Q.front)%MaxSize 这是网上的说法,我不能理解的是为什么要加MaxSize, 比如rear=6,front=1,这个中间有5个元素... -
【剑指offer】——由斐波拉契数列引发的递归循环问题
2020-03-06 14:47:11文章目录01斐波拉契数列02跳台阶问题03变态跳台阶04矩形覆盖05兔子繁殖问题 01斐波拉契数列 题目描述 思路:斐波拉切的公式为: F(0) = 0; F(1) = 1; F(n) = F(n-1)+F(n-2);(n>=2) 方法一:用递归解决。但是用... -
C语言 scanf 设置为%d却输入汉字出现循环问题解决
2020-03-11 12:42:50有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能... -
计算x^2=(1^2+2^2+3^2+...+n^2)/n的公式,利用C语言循环的算法怎么才能实现这个问题的呢?
2019-05-11 22:18:01Problem Description Find the biggest integer n (1 ) and an integer x to make them satisfy ...The input consists of several test cases....In one line for each case, output two integers n and x you ... -
for循环中执行setTimeout问题(任务队列的问题)
2019-06-02 22:09:00for(var i=0;i<8;i++){ setTimeout(function () { console.log(i) },0) ...输出了8次8,这跟js的执行顺序和作用域链有关。... 用公式表达就是:同步 => 异步(定时器 or 异步请求) => ...
-
小学1年级15以内加减法3136道题-难度低
-
读单个字符应该用字符串
-
自动化测试Python3+Selenium3+Unittest
-
【Python-随到随学】 FLask第一周
-
Android开发常用功能大集合。以及知识点的详解代码
-
使用vue搭建微信H5公众号项目
-
搜狐算法大赛:主要实体词情绪识别 baseline
-
一天学完MySQL数据库
-
pycharm链接
-
2021年 系统分析师 系列课
-
电商后台管理第一天复习01
-
QtWidgets相关的技术分享
-
【爱码农】C#制作MDI文本编辑器
-
web项目从myeclipse转移到IDEA中,一直无法连接到server的问题解决方案
-
NLP自然语言处理
-
廖雪峰的官方网站的python题目及python基础代码
-
JavaFx和SpringBoot搭建的实用小工具集合
-
工程制图 AutoCAD 2012 从二维到三维
-
旋转图像
-
golang缓存方式逐行读取文件内容练习