ITPUB论坛-中国最专业的IT技术社区

 找回密码
 注册
查看: 941|回复: 12

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

[复制链接]
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
发表于 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 .

论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 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

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 2017-10-22 17:18 | 显示全部楼层
1位数对1位数:0
1位数对2位数:
1 -> 10 -19 ,21,31,41,51,61,...
2-> 12, 20-29, 32, 42 ...

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 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

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 2017-10-22 18:39 | 显示全部楼层
某个数字出现多次的数不用列举,比如10,1110和1100是一样的

使用道具 举报

回复
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
发表于 2017-10-23 21:45 | 显示全部楼层
这么傻算是没有前途的。应该用排列组合方法:
含"1"的总共有几个?这里面又分:1位数,2位数,3位数,...前面结果可被后面利用。所有含1的互为朋友数。
含"2"不含1的总共有几个?这些也互为朋友数。
含"3"不含1,2的总共有几个?这些也互为朋友数。
......

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 2017-10-24 07:52 | 显示全部楼层
newkid 发表于 2017-10-23 21:45
这么傻算是没有前途的。应该用排列组合方法:
含"1"的总共有几个?这里面又分:1位数,2位数,3位数,... ...

这么算也要减去重复数

使用道具 举报

回复
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
发表于 2017-10-24 21:32 | 显示全部楼层
〇〇 发表于 2017-10-24 07:52
这么算也要减去重复数

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

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 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

使用道具 举报

回复
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
发表于 2017-10-25 11:11 | 显示全部楼层
〇〇 发表于 2017-10-25 09:04
1的朋友数中:
1位数没有
2位数:10个1在十位 +9个1在个位 -2位都有的11

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

使用道具 举报

回复

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

本版积分规则

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