查看: 1502|回复: 12

[SQL] 欧拉计划612题:朋友数

[复制链接]
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
发表于 2017-10-22 16:56 | 显示全部楼层 |阅读模式
本帖最后由 〇〇 于 2017-10-22 16:59 编辑

两个数的10进制表示有共同的数字,则它们是朋友数 . 如1123和3981是朋友数.
Let f(n) be the number of pairs (p,q) with 1<=p<q<n such that p and q are friend numbers. f(100)=1539 . Find f(10 ^18 ) mod 1000267129 .

论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-10-22 17:06 | 显示全部楼层
with t as(select level n from dual connect by level<100)
select count(*)
from t,t t1
where 1<=t.n and t.n<t1.n
and instr(translate(t.n,t1.n,'aaaa'),'a')>0

  COUNT(*)
----------
      1539

使用道具 举报

回复
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-10-22 17:18 | 显示全部楼层
1位数对1位数:0
1位数对2位数:
1 -> 10 -19 ,21,31,41,51,61,...
2-> 12, 20-29, 32, 42 ...

使用道具 举报

回复
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-10-22 18:08 | 显示全部楼层
f(101)-f(100):
with t as(select level n from dual connect by level<101)
select t.n,t1.n
from t,t t1
where 1<=t.n and t.n<t1.n
and instr(translate(t.n,t1.n,'aaaa'),'a')>0
minus
select t.n,t1.n
from t,t t1
where 1<=t.n and t.n<t1.n and t1.n<100
and instr(translate(t.n,t1.n,'aaaa'),'a')>0;

    N          N
----- ----------
    1        100
   10        100
   11        100
   12        100
   13        100
   14        100
   15        100
   16        100
   17        100
   18        100
   19        100
   20        100
   21        100
   30        100
   31        100
   40        100
   41        100
   50        100
   51        100
   60        100
   61        100
   70        100
   71        100
   80        100
   81        100
   90        100
   91        100

使用道具 举报

回复
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-10-22 18:39 | 显示全部楼层
某个数字出现多次的数不用列举,比如10,1110和1100是一样的

使用道具 举报

回复
论坛徽章:
526
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
发表于 2017-10-23 21:45 | 显示全部楼层
这么傻算是没有前途的。应该用排列组合方法:
含"1"的总共有几个?这里面又分:1位数,2位数,3位数,...前面结果可被后面利用。所有含1的互为朋友数。
含"2"不含1的总共有几个?这些也互为朋友数。
含"3"不含1,2的总共有几个?这些也互为朋友数。
......

使用道具 举报

回复
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-10-24 07:52 | 显示全部楼层
newkid 发表于 2017-10-23 21:45
这么傻算是没有前途的。应该用排列组合方法:
含"1"的总共有几个?这里面又分:1位数,2位数,3位数,... ...

这么算也要减去重复数

使用道具 举报

回复
论坛徽章:
526
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
发表于 2017-10-24 21:32 | 显示全部楼层
〇〇 发表于 2017-10-24 07:52
这么算也要减去重复数

确实,这个分类法不是互相隔离的。
另一种思路:
考虑两个朋友数之间只有一个共同数,两个共同数,三个....
虽然还是很繁复,但是毕竟可以算出来。

使用道具 举报

回复
论坛徽章:
401
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-10-25 09:04 | 显示全部楼层
1的朋友数中:
1位数没有
2位数:10个1在十位 +9个1在个位 -2位都有的11
3位数:100个1在百位 +100个1在十位 +9个1在个位 -2位都有的11,101,121,112,....+3位都有的111

使用道具 举报

回复
论坛徽章:
526
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
发表于 2017-10-25 11:11 | 显示全部楼层
〇〇 发表于 2017-10-25 09:04
1的朋友数中:
1位数没有
2位数:10个1在十位 +9个1在个位 -2位都有的11

你这方法也不能隔离,比如1的朋友数15和2的朋友数25之间也有关系。
必须得找出能够完全隔离的又不遗漏的划分子集的方法,我上面说的就是一种。

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

第67期:Neo4j图数据库平台架构最佳实践
【微学堂】10月18日 20:00(周四)

当下,数据的规模和类型每时每刻都在呈几何级数的增长,仅能够管理大量的数据是不够的,关键是能从海量数据中发掘出有用的信息,特别是数据之间的关联,能高效存储和处理数据之间关联的新型数据库为图数据库。 本讲座将介绍Neo4j图数据库的基本概念、设计特点、架构和经典应用场景实战分享。

进入课堂>>
TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 
京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表