ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2019函数公式学习大典 不用妈妈陪默写神器 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2016实战技巧学习锦囊 WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 6091|回复: 16

[Excel 程序开发] [第17期] 乘方[已总结]

[复制链接]

TA的精华主题

TA的得分主题

发表于 2006-11-1 16:12 | 显示全部楼层 |阅读模式
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

本期题目比较简单:

 


[此贴子已经被作者于2006-11-21 0:44:08编辑过]
单选投票, 共有 4 人参与投票

距结束还有: 3651 天25 分钟

您所在的用户组没有投票权限

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

发表于 2006-11-4 16:40 | 显示全部楼层

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

发表于 2006-11-6 12:47 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

狼版主说这道题简单,但我感觉比前两期都困难了不少,主要就因为15位这个大数字,感觉就像是一个菜鸟过滤器,把我这类投机取巧的菜鸟都给滤出来了。

第二个函数比较简单,很快就出来了,而且速度也不错。倒是第一个函数虽然做法有不少,但是数字一大耗费时间就狂增。先是学习了菊花版主的数组课,来用数组做,结果数组的容量受限。后来用集合、字典等方法都大幅提升了速度,但还是到11、12位左右出现了速度障碍。想到了用递归做法,但函数递归调用我这个初学者还没见识过,只有尝试一下函数嵌套了。没想到试了一下自定义函数嵌套速度可以提升这么多,15位数字计算只要零点零几秒,虽然我知道更好的方法还会有很多,但我还是对现在这个算法速度比较满意了,所以先交卷吧。

感谢狼版主又让我新学了不少东西。

 


点评:

思路基本正确,但答案有误差。

[A1]=124时,[A8]=14,[A16]="121=11^2"

[A1]=125时,[A8]=15,[A16]="121=11^2"

第2个函数显然有错,请查找原因

原因找到:少写了一个+1,真晕。因为先做第二个函数,所以没做边界测试。后来做第一个函数倒是都加上1了。

Function maxpower() As String
Dim p#
p = CDbl(Range("a1").Value)
If p > 1 Then
For y = 2 To Int(Log(p) / Log(2)) + 1
For x = Int(p ^ (1 / y)) + 1 To 1 Step -1
s = x ^ y
If s <= p Then Exit For
Next x
If s > maxs Then
maxs = s
maxx = x
maxy = y
End If
Next y
maxpower = maxs & "=" & maxx & "^" & maxy
Else
maxpower = "1=1^2"
End If

Application.Volatile
End Function

[此贴子已经被作者于2006-11-21 8:58:26编辑过]

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

发表于 2006-11-10 00:22 | 显示全部楼层

第一次答题有错误,现重新答题。


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

发表于 2006-11-10 00:42 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

刚才的答题又错了,现重新上传。


点评:

思路基本正确,但答案有误差。

[A1]=124时,[A8]=14,[A16]="121=11^2"

[A1]=125时,[A8]=14,[A16]="121=11^2"

显然有错,请查找原因

[此贴子已经被northwolves于2006-11-20 21:23:34编辑过]

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

发表于 2006-11-14 11:03 | 显示全部楼层

试下, 速度还可以, 版主帮看看结果是不是对的.

Function powercount(dinput As Double) As Double
    Dim i As Integer
    Dim j As Integer
    Dim tmp As String
    Dim tmpArr(1 To 15) As Integer
    Dim dTmp As Double
    Dim dTmp1 As Double
    tmpArr(1) = 2
    tmpArr(2) = 3
    tmpArr(3) = 5
    tmpArr(4) = 7
    tmpArr(5) = 11
    tmpArr(6) = 13
    tmpArr(7) = 17
    tmpArr(8) = 19
    tmpArr(9) = 23
    tmpArr(10) = 29
    tmpArr(11) = 31
    tmpArr(12) = 37
    tmpArr(13) = 41
    tmpArr(14) = 43
    tmpArr(15) = 47
    powercount = 1
    For i = 15 To 1 Step -1
        dTmp = powerCount1(dinput, tmpArr(i))
        If dTmp > 0 Then
            powercount = powercount + dTmp - 1
            For j = i - 1 To 1 Step -1
                dTmp1 = powerCount1(dTmp, tmpArr(j))
                If dTmp1 > 0 Then
                    powercount = powercount - dTmp1 + 1
                End If
            Next j
        End If
    Next i
   
End Function

Function maxpower(dinput As Double) As String
    Dim tmp As Double
    Dim tmpStr As String
    Dim tmpL As Double
    tmpStr = ""
   
    For i = 2 To dinput
        tmpL = Int(dinput ^ (1 / i))
        If tmpL = 1 Then
            Exit For
        Else
            'when the difference is very small, some strange thing happen
            '------------------------------------------------------------
            If tmpL ^ i > dinput Then
                tmpL = tmpL - 1
            End If
            If (tmpL + 1) ^ i = dinput Then
                tmpL = tmpL + 1
            End If
            '-----------------------------------------------------------
            If tmpL ^ i > tmp Then
                tmp = tmpL ^ i
               
                tmpStr = tmpL & "^" & i
            End If
        End If
    Next i
    maxpower = tmp & "=" & tmpStr
End Function
Function powerCount1(dinput As Double, ibase As Integer) As Double
    Dim tmpL As Double
    tmpL = Int(dinput ^ (1 / ibase))
    If tmpL = 1 Then
        powerCount1 = 0
    Else
        If tmpL ^ ibase > dinput Then
            tmpL = tmpL - 1
        End If
        If (tmpL + 1) ^ ibase = dinput Then
            tmpL = tmpL + 1
        End If
        powerCount1 = tmpL
    End If
End Function



点评:

结果正确,各种情况考虑得比较周到。

[此贴子已经被northwolves于2006-11-20 21:29:03编辑过]

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

 楼主| 发表于 2006-11-20 22:21 | 显示全部楼层

附:我的解法:

Private Const p1 As String = "{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}"
Private Const p2 As String = "{6,10,14,15,21,22,25,26,33,34,35,38,39,46}"


Function powercount(ByVal r As Range) As Long
powercount = Evaluate("SUMPRODUCT(INT(" & r & "^(1/" & p1 & ")))-SUMPRODUCT(INT(" & r & "^(1/" & p2 & ")))")  '前者15个质数,1被计数15次,后者14个质数,1被计数14次,正好抵消
End Function


Function maxpower(ByVal r As Range) As String
Dim largest As Double, power As Byte, p3 As String
largest = Evaluate("MAX(INT(" & r & "^(1/" & p1 & "))^" & p1 & ")")
p3 = largest & "^(1/" & p1 & "))"
power = Evaluate("1/Max((INT(" & p3 & "=" & p3 & "*(1/" & p1 & "))")
maxpower = largest & "=" & largest ^ (1 / power) & "^" & power
End Function


 

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?免费注册

x

TA的精华主题

TA的得分主题

 楼主| 发表于 2006-11-20 22:24 | 显示全部楼层

附:我的解法:

Private Const p1 As String = "{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}"
Private Const p2 As String = "{6,10,14,15,21,22,25,26,33,34,35,38,39,46}"


Function powercount(ByVal r As Range) As Long
powercount = Evaluate("SUMPRODUCT(INT(" & r & "^(1/" & p1 & ")))-SUMPRODUCT(INT(" & r & "^(1/" & p2 & ")))")  '前者15个质数,1被计数15次,后者14个质数,1被计数14次,正好抵消
End Function


Function maxpower(ByVal r As Range) As String
Dim largest As Double, power As Byte, p3 As String
largest = Evaluate("MAX(INT(" & r & "^(1/" & p1 & "))^" & p1 & ")")
p3 = largest & "^(1/" & p1 & "))"
power = Evaluate("1/Max((INT(" & p3 & "=" & p3 & "*(1/" & p1 & "))")
maxpower = largest & "=" & largest ^ (1 / power) & "^" & power
End Function


 

TA的精华主题

TA的得分主题

 楼主| 发表于 2006-11-20 22:42 | 显示全部楼层

2006 topcoder SRM305:

Problem Statement for PowerCollector
 
 
Problem Statement
     Your friends collect butterflies and stamps, but you collect numbers. Your collection of prime numbers is the finest in three counties, and your collection of transcendental numbers has been featured on national talkshows. Lately you've decided to start collecting powers, that is, numbers that can be written in the form MK, where M and K are positive integers with K > 1. However, you're wondering how big a box you'll need to hold them all. Given a number N, represented as a String, determine how many powers lie between 1 and N, inclusive. Return the number of powers as a String with no leading zeros.
 
 
Definition
     Class: PowerCollector
Method: countPowers
Parameters: String
Returns: String
Method signature: String countPowers(String N)
(be sure your method is public)
 
    
 
 
Constraints
- N will contain between 1 and 19 characters, inclusive.
- Each character in N will be a digit ('0'-'9').
- The first character in N will not be zero ('0').
- N will represent a number between 1 and 1000000000000000000 (10^18), inclusive.
 
Examples
0) 
     "10"
 
 
Returns: "4"
 
The powers between 1 and 10 are 1, 4, 8, and 9.
 
 
1) 
     "36"
 
 
Returns: "9"
 
The powers between 1 and 36 are 1, 4, 8, 9, 16, 25, 27, 32, and 36.
 
 
2) 
     "1000000000000000000"
 
 
Returns: "1001003332"

本题由以上题目改编,并把难度适当减低。

题目是问<=N的正整数中有多少个可以被写成M^k(M,k>1)的形式.N<=10^18

由于指数不大,所以可以枚举指数k,然后考虑有多少个b满足b^k<=N.这是b<=N^(1/k),但是一个数可以被写成多种指数形式.需要去掉重复.

可以用容斥原理.我们只考虑 k = p1 * p2 * ... * pm的形式.如果k包含pi多次,很容易转化成这种形式.
对于某个k和B=[N^(1/k)],如果m为奇数,答案+B,否则-B.


TA的精华主题

TA的得分主题

 楼主| 发表于 2006-11-20 22:54 | 显示全部楼层

另附:

Perfect Power
 A perfect power is a number n of the form m^k, where m>1 is a positive integer and k>=2. If the prime factorization of n is n==p_1^(a_1)p_2^(a_2)...p_k^(a_k), then n is a perfect power iff GCD(a_1,a_2,...,a_k)>1.

Including duplications (i.e., taking all numbers up to some cutoff and taking all their powers) and taking m>1, the first few are 4, 8, 9, 16, 16, 25, 27, 32, 36, 49, 64, 64, 64, ... (Sloane's A072103). Here, 16 is duplicated since

16==2^4==4^2.
(1)

As shown by Goldbach Eric Weisstein's World of Biography, the sum of reciprocals of perfect powers (excluding 1) with duplications converges,

sum_(m==2)^inftysum_(k==2)^infty1/(m^k)==1.
(2)

The first few numbers that are perfect powers in more than one way are 16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, ... (Sloane's A117453).

The first few perfect powers without duplications are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 125, 128, ... (Sloane's A001597). Even more amazingly, the sum of the reciprocals of these numbers (excluding 1) is given by

sum_(k==2)^inftymu(k)[1-zeta(k)] approx 0.874464365...
(3)

(Sloane's A072102), where mu(k) is the Möbius function and zeta(k) is the Riemann zeta function.

The numbers of perfect powers without duplications less than 10, 10^2, 10^3, ... are 4, 13, 41, 125, 367, ... (Sloane's A070428).

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

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-19 15:47 , Processed in 0.054251 second(s), 15 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表