《用Python写网络爬虫》——1.4 编写第一个网络爬虫

1.4 编写第一个网络爬虫

为了抓取网站,我们首先需要下载包含有感兴趣数据的网页,该过程一般被称为爬取(crawling)。爬取一个网站有很多种方法,而选用哪种方法更加合适,则取决于目标网站的结构。本章中,首先会探讨如何安全地下载网页,然后会介绍如下3种爬取网站的常见方法:

爬取网站地图;

遍历每个网页的数据库ID;

跟踪网页链接。

1.4.1 下载网页

要想爬取网页,我们首先需要将其下载下来。下面的示例脚本使用Python的urllib2模块下载URL。

    import urllib2
    def download(url):
        return urllib2.urlopen(url).read()

当传入URL参数时,该函数将会下载网页并返回其HTML。不过,这个代码片段存在一个问题,即当下载网页时,我们可能会遇到一些无法控制的错误,比如请求的页面可能不存在。此时,urllib2会抛出异常,然后退出脚本。安全起见,下面再给出一个更健壮的版本,可以捕获这些异常。

    import urllib2

    def download(url):
        print 'Downloading:', url
        try:
            html = urllib2.urlopen(url).read()
        except urllib2.URLError as e:
            print 'Download error:', e.reason
            html = None
        return html

现在,当出现下载错误时,该函数能够捕获到异常,然后返回None。

1.重试下载

下载时遇到的错误经常是临时性的,比如服务器过载时返回的503 Service Unavailable错误。对于此类错误,我们可以尝试重新下载,因为这个服务器问题现在可能已解决。不过,我们不需要对所有错误都尝试重新下载。如果服务器返回的是404 Not Found这种错误,则说明该网页目前并不存在,再次尝试同样的请求一般也不会出现不同的结果。

互联网工程任务组(Internet Engineering Task Force)定义了HTTP错误的完整列表,详情可参考https://tools.ietf.org/html/rfc7231#section-6 。从该文档中,我们可以了解到4xx错误发生在请求存在问题时,而5xx错误则发生在服务端存在问题时。所以,我们只需要确保download函数在发生5xx`错误时重试下载即可。下面是支持重试下载功能的新版本 代码。

    def download(url, num_retries=2):
        print 'Downloading:', url
        try:
            html = urllib2.urlopen(url).read()
        except urllib2.URLError as e:
            print 'Download error:', e.reason
            html = None
            if num_retries > 0:
                if hasattr(e, 'code') and 500 <= e.code < 600:
                    # recursively retry 5xx HTTP errors
                    return download(url, num_retries-1)
        return html

现在,当download函数遇到5xx错误码时,将会递归调用函数自身进行重试。此外,该函数还增加了一个参数,用于设定重试下载的次数,其默认值为两次。我们在这里限制网页下载的尝试次数,是因为服务器错误可能暂时还没有解决。想要测试该函数,可以尝试下载http://httpstat.us/500 ,该网址会始终返回500错误码。

>>> download('http://httpstat.us/500')
Downloading: http://httpstat.us/500
Download error: Internal Server Error
Downloading: http://httpstat.us/500
Download error: Internal Server Error
Downloading: http://httpstat.us/500
Download error: Internal Server Error

从上面的返回结果可以看出,download函数的行为和预期一致,先尝试下载网页,在接收到500错误后,又进行了两次重试才放弃。

2.设置用户代理

默认情况下,urllib2使用Python-urllib/2.7作为用户代理下载网页内容,其中2.7是Python的版本号。如果能使用可辨识的用户代理则更好,这样可以避免我们的网络爬虫碰到一些问题。此外,也许是因为曾经历过质量不佳的Python网络爬虫造成的服务器过载,一些网站还会封禁这个默认的用户代理。比如,在使用Python默认用户代理的情况下,访问http://www.meetup.com/`` ,目前会返回如图1.3所示的访问拒绝提示。

因此,为了下载更加可靠,我们需要控制用户代理的设定。下面的代码对download函数进行了修改,设定了一个默认的用户代理“wswp”(即Web Scraping with Python的首字母缩写)。

    def download(url, user_agent='wswp', num_retries=2):
        print 'Downloading:', url
        headers = {'User-agent': user_agent}
        request = urllib2.Request(url, headers=headers)
        try:
            html = urllib2.urlopen(request).read()
        except urllib2.URLError as e:
            print 'Download error:', e.reason
            html = None
            if num_retries > 0:
                if hasattr(e, 'code') and 500 <= e.code < 600:
                    # retry 5XX HTTP errors
                    return download(url, user_agent, num_retries-1)
        return html

现在,我们拥有了一个灵活的下载函数,可以在后续示例中得到复用。该函数能够捕获异常、重试下载并设置用户代理。

1.4.2 网站地图爬虫

在第一个简单的爬虫中,我们将使用示例网站robots.txt文件中发现的网站地图来下载所有网页。为了解析网站地图,我们将会使用一个简单的正则表达式,从<loc>标签中提取出URL。而在下一章中,我们将会介绍一种更加健壮的解析方法——CSS选择器。下面是该示例爬虫的代码。

    def crawl_sitemap(url):
        # download the sitemap file
        sitemap = download(url)
        # extract the sitemap links
        links = re.findall('<loc>(.*?)</loc>', sitemap)
        # download each link
        for link in links:
            html = download(link)
            # scrape html here
            # ...

现在,运行网站地图爬虫,从示例网站中下载所有国家页面。

>>> crawl_sitemap('http://example.webscraping.com/sitemap.xml')
Downloading: http://example.webscraping.com/sitemap.xml
Downloading: http://example.webscraping.com/view/Afghanistan-1
Downloading: http://example.webscraping.com/view/Aland-Islands-2
Downloading: http://example.webscraping.com/view/Albania-3
...

可以看出,上述运行结果和我们的预期一致,不过正如前文所述,我们无法依靠Sitemap文件提供每个网页的链接。下一节中,我们将会介绍另一个简单的爬虫,该爬虫不再依赖于Sitemap文件。

1.4.3 ID遍历爬虫

本节中,我们将利用网站结构的弱点,更加轻松地访问所有内容。下面是一些示例国家的URL。

http://example.webscraping.com/view/Afghanistan-1

http://example.webscraping.com/view/Australia-2

http://example.webscraping.com/view/Brazil-3

可以看出,这些URL只在结尾处有所区别,包括国家名(作为页面别名)和ID。在URL中包含页面别名是非常普遍的做法,可以对搜索引擎优化起到帮助作用。一般情况下,Web服务器会忽略这个字符串,只使用ID来匹配数据库中的相关记录。下面我们将其移除,加载http://example.`` ``webscraping.com/view/1,测试示例网站中的链接是否仍然可用。测试结果如图1.4所示。

从图1.4中可以看出,网页依然可以加载成功,也就是说该方法是有用的。现在,我们就可以忽略页面别名,只遍历ID来下载所有国家的页面。下面是使用了该技巧的代码片段。

    import itertools
    for page in itertools.count(1):
        url = 'http://example.webscraping.com/view/-%d' % page
        html = download(url)
        if html is None:
            break
        else:
            # success - can scrape the result
            pass

在这段代码中,我们对ID进行遍历,直到出现下载错误时停止,我们假设此时已到达最后一个国家的页面。不过,这种实现方式存在一个缺陷,那就是某些记录可能已被删除,数据库ID之间并不是连续的。此时,只要访问到某个间隔点,爬虫就会立即退出。下面是这段代码的改进版本,在该版本中连续发生多次下载错误后才会退出程序。

    # maximum number of consecutive download errors allowed
    max_errors = 5
    # current number of consecutive download errors
    num_errors = 0
    for page in itertools.count(1):
        url = 'http://example.webscraping.com/view/-%d' % page
        html = download(url)
        if html is None:
            # received an error trying to download this webpage
            num_errors += 1
            if num_errors == max_errors:
                # reached maximum number of
                # consecutive errors so exit
                break
        else:
            # success - can scrape the result
            # ...
            num_errors = 0

上面代码中实现的爬虫需要连续5次下载错误才会停止遍历,这样就很大程度上降低了遇到被删除记录时过早停止遍历的风险。

在爬取网站时,遍历ID是一个很便捷的方法,但是和网站地图爬虫一样,这种方法也无法保证始终可用。比如,一些网站会检查页面别名是否满足预期,如果不是,则会返回404 Not Found错误。而另一些网站则会使用非连续大数作为ID,或是不使用数值作为ID,此时遍历就难以发挥其作用了。例如,Amazon使用ISBN作为图书ID,这种编码包含至少10位数字。使用ID对Amazon的图书进行遍历需要测试数十亿次,因此这种方法肯定不是抓取该站内容最高效的方法。

1.4.4 链接爬虫

到目前为止,我们已经利用示例网站的结构特点实现了两个简单爬虫,用于下载所有的国家页面。只要这两种技术可用,就应当使用其进行爬取,因为这两种方法最小化了需要下载的网页数量。不过,对于另一些网站,我们需要让爬虫表现得更像普通用户,跟踪链接,访问感兴趣的内容。

通过跟踪所有链接的方式,我们可以很容易地下载整个网站的页面。但是,这种方法会下载大量我们并不需要的网页。例如,我们想要从一个在线论坛中抓取用户账号详情页,那么此时我们只需要下载账号页,而不需要下载讨论贴的页面。本节中的链接爬虫将使用正则表达式来确定需要下载哪些页面。下面是这段代码的初始版本。

    import re

    def link_crawler(seed_url, link_regex):
        """Crawl from the given seed URL following links matched by link_regex
        """
        crawl_queue = [seed_url]
        while crawl_queue:
            url = crawl_queue.pop()
            html = download(url)
            # filter for links matching our regular expression
            for link in get_links(html):
                if re.match(link_regex, link):
                    crawl_queue.append(link)

    def get_links(html):
        """Return a list of links from html
        """
        # a regular expression to extract all links from the webpage
        webpage_regex = re.compile('<a[^>]+href=["\'](.*?)["\']',
            re.IGNORECASE)
        # list of all links from the webpage
        return webpage_regex.findall(html)

要运行这段代码,只需要调用link_crawler函数,并传入两个参数:要爬取的网站URL和用于跟踪链接的正则表达式。对于示例网站,我们想要爬取的是国家列表索引页和国家页面。其中,索引页链接格式如下。

http://example.webscraping.com/index/1

http://example.webscraping.com/index/2

国家页链接格式如下。

http://example.webscraping.com/view/Afghanistan-1

http://example.webscraping.com/view/Aland-Islands-2

因此,我们可以用/(index|view)/这个简单的正则表达式来匹配这两类网页。当爬虫使用这些输入参数运行时会发生什么呢?你会发现我们得到了如下的下载错误。

    >>> link_crawler('http://example.webscraping.com',
        '/(index|view)')
    Downloading: http://example.webscraping.com
    Downloading: /index/1
    Traceback (most recent call last):
        ...
    ValueError: unknown url type: /index/1

可以看出,问题出在下载/index/1时,该链接只有网页的路径部分,而没有协议和服务器部分,也就是说这是一个相对链接。由于浏览器知道你正在浏览哪个网页,所以在浏览器浏览时,相对链接是能够正常工作的。但是,urllib2是无法获知上下文的。为了让urllib2能够定位网页,我们需要将链接转换为绝对链接的形式,以便包含定位网页的所有细节。如你所愿,Python中确实有用来实现这一功能的模块,该模块称为urlparse。下面是link_crawler的改进版本,使用了urlparse模块来创建绝对路径。

    import urlparse
    def link_crawler(seed_url, link_regex):
        """Crawl from the given seed URL following links matched by link_regex
        """
        crawl_queue = [seed_url]
        while crawl_queue:
            url = crawl_queue.pop()
            html = download(url)
            for link in get_links(html):
                if re.match(link_regex, link):
                    link = urlparse.urljoin(seed_url, link)
                    crawl_queue.append(link)

当你运行这段代码时,会发现虽然网页下载没有出现错误,但是同样的地点总是会被不断下载到。这是因为这些地点相互之间存在链接。比如,澳大利亚链接到了南极洲,而南极洲也存在到澳大利亚的链接,此时爬虫就会在它们之间不断循环下去。要想避免重复爬取相同的链接,我们需要记录哪些链接已经被爬取过。下面是修改后的link_crawler函数,已具备存储已发现URL的功能,可以避免重复下载。

    def link_crawler(seed_url, link_regex):
        crawl_queue = [seed_url]
        # keep track which URL's have seen before
        seen = set(crawl_queue)
        while crawl_queue:
            url = crawl_queue.pop()
            html = download(url)
            for link in get_links(html):
                # check if link matches expected regex
                if re.match(link_regex, link):
                    # form absolute link
                    link = urlparse.urljoin(seed_url, link)
                    # check if have already seen this link
                    if link not in seen:
                        seen.add(link)
                        crawl_queue.append(link)

当运行该脚本时,它会爬取所有地点,并且能够如期停止。最终,我们得到了一个可用的爬虫!
高级功能

现在,让我们为链接爬虫添加一些功能,使其在爬取其他网站时更加有用。
解析robots.txt

首先,我们需要解析robots.txt文件,以避免下载禁止爬取的URL。使用Python自带的robotparser模块,就可以轻松完成这项工作,如下面的代码所示。

>>> import robotparser
>>> rp = robotparser.RobotFileParser()
>>> rp.set_url('http://example.webscraping.com/robots.txt')
>>> rp.read()
>>> url = 'http://example.webscraping.com'
>>> user_agent = 'BadCrawler'
>>> rp.can_fetch(user_agent, url)
False
>>> user_agent = 'GoodCrawler'
>>> rp.can_fetch(user_agent, url)
True

robotparser模块首先加载robots.txt文件,然后通过can_fetch()函数确定指定的用户代理是否允许访问网页。在本例中,当用户代理设置为 'BadCrawler' 时,robotparser模块会返回结果表明无法获取网页,这和示例网站robots.txt``的定义一样。

为了将该功能集成到爬虫中,我们需要在crawl循环中添加该检查。

    ...
    while crawl_queue:
        url = crawl_queue.pop()
        # check url passes robots.txt restrictions
        if rp.can_fetch(user_agent, url):
            ...
        else:
            print 'Blocked by robots.txt:', url

支持代理

有时我们需要使用代理访问某个网站。比如,Netflix屏蔽了美国以外的大多数国家。使用urllib2支持代理并没有想象中那么容易(可以尝试使用更友好的Python HTTP模块requests来实现该功能,其文档地址为http://docs.python-requests.org/) 。下面是使用urllib2支持代理的代码。

    proxy = ...
    opener = urllib2.build_opener()
    proxy_params = {urlparse.urlparse(url).scheme: proxy}
    opener.add_handler(urllib2.ProxyHandler(proxy_params))
    response = opener.open(request)

下面是集成了该功能的新版本download函数。

    def download(url, user_agent='wswp', proxy=None, num_retries=2):
        print 'Downloading:', url
        headers = {'User-agent': user_agent}
        request = urllib2.Request(url, headers=headers)

        opener = urllib2.build_opener()
        if proxy:
            proxy_params = {urlparse.urlparse(url).scheme: proxy}
            opener.add_handler(urllib2.ProxyHandler(proxy_params))
        try:
            html = opener.open(request).read()
        except urllib2.URLError as e:
            print 'Download error:', e.reason
            html = None
            if num_retries > 0:
                if hasattr(e, 'code') and 500 <= e.code < 600:
                # retry 5XX HTTP errors
                html = download(url, user_agent, proxy,
                    num_retries-1)
        return html

下载限速

如果我们爬取网站的速度过快,就会面临被封禁或是造成服务器过载的风险。为了降低这些风险,我们可以在两次下载之间添加延时,从而对爬虫限速。下面是实现了该功能的类的代码。

    class Throttle:
        """Add a delay between downloads to the same domain
        """
        def __init__(self, delay):
            # amount of delay between downloads for each domain
            self.delay = delay
            # timestamp of when a domain was last accessed
            self.domains = {}

        def wait(self, url):
            domain = urlparse.urlparse(url).netloc
            last_accessed = self.domains.get(domain)

            if self.delay > 0 and last_accessed is not None:
                sleep_secs = self.delay - (datetime.datetime.now() -
                    last_accessed).seconds
                if sleep_secs > 0:
                    # domain has been accessed recently
                    # so need to sleep
                    time.sleep(sleep_secs)
            # update the last accessed time
            self.domains[domain] = datetime.datetime.now()

Throttle类记录了每个域名上次访问的时间,如果当前时间距离上次访问时间小于指定延时,则执行睡眠操作。我们可以在每次下载之前调用Throttle对爬虫进行限速。

    throttle = Throttle(delay)
    ...
    throttle.wait(url)
    result = download(url, headers, proxy=proxy,
        num_retries=num_retries)

避免爬虫陷阱

目前,我们的爬虫会跟踪所有之前没有访问过的链接。但是,一些网站会动态生成页面内容,这样就会出现无限多的网页。比如,网站有一个在线日历功能,提供了可以访问下个月和下一年的链接,那么下个月的页面中同样会包含访问再下个月的链接,这样页面就会无止境地链接下去。这种情况被称为爬虫陷阱

想要避免陷入爬虫陷阱,一个简单的方法是记录到达当前网页经过了多少个链接,也就是深度。当到达最大深度时,爬虫就不再向队列中添加该网页中的链接了。要实现这一功能,我们需要修改seen变量。该变量原先只记录访问过的网页链接,现在修改为一个字典,增加了页面深度的记录。

    def link_crawler(..., max_depth=2):
        max_depth = 2
        seen = {}
        ...
        depth = seen[url]
        if depth != max_depth:
            for link in links:
                if link not in seen:
                    seen[link] = depth + 1
                    crawl_queue.append(link)

现在有了这一功能,我们就有信心爬虫最终一定能够完成。如果想要禁用该功能,只需将max_depth设为一个负数即可,此时当前深度永远不会与之相等。

最终版本

这个高级链接爬虫的完整源代码可以在https://bitbucket.org/ wswp/code/src/tip/chapter01/link_crawler3.py下载得到。要测试这段代码,我们可以将用户代理设置为BadCrawler,也就是本章前文所述的被robots.txt屏蔽了的那个用户代理。从下面的运行结果中可以看出,爬虫果然被屏蔽了,代码启动后马上就会结束。

>>> seed_url = 'http://example.webscraping.com/index'
>>> link_regex = '/(index|view)'
>>> link_crawler(seed_url, link_regex, user_agent='BadCrawler')
Blocked by robots.txt: http://example.webscraping.com/

现在,让我们使用默认的用户代理,并将最大深度设置为1,这样只有主页上的链接才会被下载。

>>> link_crawler(seed_url, link_regex, max_depth=1)
Downloading: http://example.webscraping.com//index
Downloading: http://example.webscraping.com/index/1
Downloading: http://example.webscraping.com/view/Antigua-and-Barbuda-10
Downloading: http://example.webscraping.com/view/Antarctica-9
Downloading: http://example.webscraping.com/view/Anguilla-8
Downloading: http://example.webscraping.com/view/Angola-7
Downloading: http://example.webscraping.com/view/Andorra-6
Downloading: http://example.webscraping.com/view/American-Samoa-5
Downloading: http://example.webscraping.com/view/Algeria-4
Downloading: http://example.webscraping.com/view/Albania-3
Downloading: http://example.webscraping.com/view/Aland-Islands-2
Downloading: http://example.webscraping.com/view/Afghanistan-1

和预期一样,爬虫在下载完国家列表的第一页之后就停止了。

时间: 2024-09-17 04:42:06

《用Python写网络爬虫》——1.4 编写第一个网络爬虫的相关文章

《用Python写网络爬虫》——导读

前 言 互联网包含了迄今为止最有用的数据集,并且大部分可以免费公开访问.但是,这些数据难以复用.它们被嵌入在网站的结构和样式当中,需要抽取出来才能使用.从网页中抽取数据的过程又被称为网络爬虫.随着越来越多的信息被发布到网络上,网络爬虫也变得越来越有用. 目 录 第1章 网络爬虫简介 1.1 网络爬虫何时有用1.2 网络爬虫是否合法1.3 背景调研 1.3.1 检查robots.txt 1.3.2 检查网站地图 1.3.3 估算网站大小 1.3.4 识别网站所用技术 1.3.5 寻找网站所有者1.

Android编写简单的网络爬虫

一.网络爬虫的基本知识 网络爬虫通过遍历互联网络,把网络中的相关网页全部抓取过来,这体现了爬的概念.爬虫如何遍历网络呢,互联网可以看做是一张大图,每个页面看做其中的一个节点,页面的连接看做是有向边.图的遍历方式分为宽度遍历和深度遍历,但是深度遍历可能会在深度上过深的遍历或者陷入黑洞.所以,大多数爬虫不采用这种形式.另一方面,爬虫在按照宽度优先遍历的方式时候,会给待遍历的网页赋予一定优先级,这种叫做带偏好的遍历. 实际的爬虫是从一系列的种子链接开始.种子链接是起始节点,种子页面的超链接指向的页面是

解决python写的爬虫程序抓取到的网页是乱码的问题

在开发自用爬虫过程中,有的网页是utf-8,有的是gb2312,有的是gbk,怎么办? 下面所说的都是针对python2.7 如果不加处理,采集到的都是乱码,解决的方法是将html处理成统一的utf-8编码. #chardet 需要下载安装 import chardet #抓取网页html html_1 = urllib2.urlopen(line,timeout=120).read() #print html_1 mychar=chardet.detect(html_1) #print myc

教你如何编写简单的网络爬虫_java

一.网络爬虫的基本知识 网络爬虫通过遍历互联网络,把网络中的相关网页全部抓取过来,这体现了爬的概念.爬虫如何遍历网络呢,互联网可以看做是一张大图,每个页面看做其中的一个节点,页面的连接看做是有向边.图的遍历方式分为宽度遍历和深度遍历,但是深度遍历可能会在深度上过深的遍历或者陷入黑洞.所以,大多数爬虫不采用这种形式.另一方面,爬虫在按照宽度优先遍历的方式时候,会给待遍历的网页赋予一定优先级,这种叫做带偏好的遍历. 实际的爬虫是从一系列的种子链接开始.种子链接是起始节点,种子页面的超链接指向的页面是

android-关于用python写服务器的问题

问题描述 关于用python写服务器的问题 本人学生,最近在做课程设计,写一个Android的移动应用,需要编写一个服务器,同学推荐我用python来写,不知道好写么,另外写完后连接java写的客户端好连接么?现在初步打算是在手机上装好客户端,然后电脑上运行服务器后,手机连上电脑的WIFI来实现客户端和服务器的连接,这样好么?ps:本人没学过python,如果好写的话就去现学 解决方案 好写,python做一个网站或者web服务,java通过web接口调用.不需要网络连接这些底层的编程知识. 解

用Python写成的MCR乐队敲诈者木马:这种操作很朋克!

本文讲的是用Python写成的MCR乐队敲诈者木马:这种操作很朋克!,几年前,敲诈者木马还是一个默默无闻的木马种类.然而,由于其极强的破坏力和直接且丰厚的财富回报,敲诈者木马这几年已经一跃成为曝光率最高的木马类型--甚至超越了盗号木马.远控木马.网购木马这传统三强.与此同时,各种敲诈者木马也在不断推陈出新,变着花样地出现在分析人员的视野中. 去年,360安全团队就发现了一款使用PHP语言编写的敲诈者木马(具体内容参考<用世界上最好的编程语言写成的敲诈者木马>).最近,一款使用Python语言编

【求助】用Python写出一个遍历网站所有url的小工具

问题描述 [求助]用Python写出一个遍历网站所有url的小工具 用Python 怎么写出一个 遍历网站所有url的小工具, 包括首页的url和所有子网页url 不能有重复的url,我自己写的只能遍历一个网页的 首页,子网页的遍历不出来,新人 没币 ,求好心人帮助!!! 解决方案 http://www.cnblogs.com/fnng/p/3576154.htmlhttp://www.oschina.net/code/list_releted_codes?id=25402 解决方案二: htt

Java实现爬虫给App提供数据(Jsoup 网络爬虫)_java

一.需求 最近基于 Material Design 重构了自己的新闻 App,数据来源是个问题. 有前人分析了知乎日报.凤凰新闻等 API,根据相应的 URL 可以获取新闻的 JSON 数据.为了锻炼写代码能力,笔者打算爬虫新闻页面,自己获取数据构建 API. 二.效果图 下图是原网站的页面 爬虫获取了数据,展示到 APP 手机端 三.爬虫思路 关于App 的实现过程可以参看这几篇文章,本文主要讲解一下如何爬虫数据. Android下录制App操作生成Gif动态图的全过程 :http://www

母牛-用Python写,急求解答

问题描述 用Python写,急求解答 Part H ( points) 有一头母牛,它每年年初生一头小母牛.每头小母牛从第四个年头开始,每年年初也生一头小母牛.编写程序,输入一个正整数N,求在第N年的时候,共有多少头母牛? 解决方案 楼上的写错了 def row_count(n): if n==0: return 1 if n==1: return 2 if n==2: return 3 if n==3: return 4 else: return row_count(n-3)+row_coun